Standard Code Library

[TOC]

1. Math

1.1 Matrix

1.1.1 matrix class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//POJ3420
const int MAXN = 1005;
const int MAXM = 1005;
struct Matrix{
int n, m;
int a[MAXN][MAXM];
void clear(){
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator +(const Matrix &b) const {
Matrix tmp;
tmp.n = n, tmp.m = m;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= m; ++j)
tmp.a[i][j] = a[i][j] + b.a[i][j];
return tmp;
}
Matrix operator -(const Matrix &b) const{
Matrix tmp;
tmp.n = n, tmp.m = m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
tmp.a[i][j] = a[i][j] - b.a[i][j];
return tmp;
}
Matrix operator *(const Matrix &b) const{
Matrix tmp;
tmp.clear();
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < m; ++k)
tmp.a[i][j] += a[i][k] * b.a[k][j];
return tmp;
}
};

1.1.2 gaussian elimination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//POJ 1830
const int MAXN = 1005;
const int MAXM = 1005;
const double EPS = 1e-8;
struct Matrix{
int n, m;
int a[MAXN][MAXM];
void clear(){
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator +(const Matrix &b) const {
Matrix tmp;
tmp.n = n, tmp.m = m;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= m; ++j)
tmp.a[i][j] = a[i][j] + b.a[i][j];
return tmp;
}
Matrix operator -(const Matrix &b) const{
Matrix tmp;
tmp.n = n, tmp.m = m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
tmp.a[i][j] = a[i][j] - b.a[i][j];
return tmp;
}
Matrix operator *(const Matrix &b) const{
Matrix tmp;
tmp.clear();
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < m; ++k)
tmp.a[i][j] += a[i][k] * b.a[k][j];
return tmp;
}
};
inline int solve(double a[][MAXN], bool l[], double ans[], const int &n){
int res = 0, r = 0;
for (int i = 0; i < n; ++i)
l[i] = false;
for (int i = 0; i < n; ++i){
for (int j = r; j < n; ++j){
if (fabs(a[j][i]) > EPS){
for (int k = i; k <= n; ++k){
swap(a[j][k], a[r][k]);
}
}
}
if (fabs(a[r][i]) < EPS){
++res;
continue;
}
for (int j = 0; j < n; ++j){
if (j != r && fabs(a[j][i]) > EPS){
double tmp = a[j][i] / a[r][i];
for (int k = i; k <= n; ++k)
a[j][k] -= tmp * a[r][k];
}
}
l[i] = true;
++r;
}
for (int i = 0; i < n; ++i){
if (!l[i]) continue;
for(int j = 0; j < n; ++j){
if(fabs(a[j][i]) > 0){
ans[i] = a[j][n] / a[j][i];
}
}
}
return res;
}

1.1.3 matrix inverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
inline vector<double> operator *(vector<double> a, dobule b){
int n = a.size();
vector<double> res(n, 0);
for(int i = 0; i < n; ++i){
res[i] = a[i] * b;
}
return res;
}
inline vector<double> operator -(vector<double> a, vector<double> b){
int n = a.size();
vector<double> res(n, 0);
for(int i = 0; i < n; ++i){
res[i] = a[i] - b[i];
}
return res;
}
inline void inverse(vector<double> A[], vector<double> C[], int n){
for(int i = 0; i < n; ++i){
C[i] = vector<double>(n, 0);
}
for(int i = 0; i < n; ++i){
C[i][i] = 1;
}
for(int i = 0; i < n; ++i){
for(int j = i; j < n; ++j){
if(fabs(A[j][i]) > 0){
swap(A[i], A[j]);
swap(C[i], C[j]);
break;
}
}
C[i] = C[i] * (1 / A[i][i]);
A[i] = A[i] * (1 / A[i][i]);
for(int j = 0; j < n; ++j){
if(j != i && fabs(A[j][i]) > 0)){
C[j] = C[j] - C[j] * A[j][i];
A[j] = A[j] - A[i] * A[j][i];
}
}
}
}

1.2 Integer & surplus

1.2.1 euclid

1
2
3
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}

1.2.2 extended euclid

1
2
3
4
5
6
7
8
9
int extend_gcd(int a, int b, int &x, int &y){
if (b == 0){
x = 1, y = 0;
return a;
}
int res = extend_gcd(b, a % b, y, x);
y -= x * (a / b);
return res;
}

1.2.3 modulo linear equation

1
2
3
4
5
6
7
8
9
10
11
12
vector<LL> line_mod_equation(LL a, LL b, LL n){
LL x, y;
LL d = extend_gcd(a, n, x, y);
vector<LL> ans;
if (b % d == 0){
x %= n, x += n, x %= n;
ans.push_back(x * (b / d) % (n / d));
for (LL i = 1; i < d; ++i)
ans.push_back((ans[0] + i * n / d) % n);
}
return ans;
}

1.2.4 chinese remainder theorem

1
2
3
4
5
6
7
8
9
10
11
12
int CRT(int a[], int m[], int n){
int M = 1;
for (int i = 0; i < n; ++i) M *= m[i];
int ret = 0;
for (int i = 0; i < n; ++i){
int x, y;
int tm = M / m[i];
extend_gcd(tm, m[i], x, y);
ret = (ret + tm * x * a[i]) % M;
}
return (ret + M) % M;
}

1.2.5 primitive root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> a;
bool g_test(int g, int p){
for(int i = 0; i < a.size(); ++i){
if(pow_mod(g, (p - 1) / a[i], p) == 1)
return 0;
}
return 1;
}
int primitive_root(int p){
int tmp = p - 1;
for(int i = 2; i <= tmp / i; ++i){
if(tmp % i == 0){
a.push_back(i);
while(tmp % i == 0){
tmp /= i;
}
}
}
if(tmp != 1){
a.push_back(tmp);
}
int g = 1;
while(1){
if(g_test(g, p)){
return g;
}
++g;
}
}

1.2.6 modulo square

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int modsqr(int a, int n){
int b, k, i, x;
if(n == 2) return a % n;
if(pow_mod(a, (n - 1) >> 1, n) == 1){
if(n % 4 == 3){
x = pow_mod(a, (n + 1) >> 2, n);
}
else{
for(b = 1; pow_mod(b, (n - 1) >> 1, n) == 1; ++b);
i = (n - 1) >> 1;
k = 0;
do{
i >>= 1;
k >>= 1;
if((pow_mod(a, i, n) * pow_mod(b, k, n) + 1) % n == 0){
k += (n - 1) >> 1;
}
}while(i & 1 == 0);
x = (pow_mod(a, (i + 1) >> 1, n) * pow_mod(b, k >> 1, n)) % n;
}
if((x << 1) > n)
x = n - x;
return x;
}
return -1;
}

1.2.7 discrete logarithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LL discrete_log(int x, int n, int m){
map<LL, int> rec;
int s = (int)(sqrt((double)m));
while((LL)s * s <= m) ++s;
LL cur = 1;
for(int i = 0; i < s; ++i){
rec[cur] = i;
cur = cur * x % m;
}
LL mul = cur;
cur = 1;
for(int i = 0; i < s; ++i){
LL more = (LL)n * pow_mod(cur, m - 2, m) % m;
if(rec.count(more)){
return i * s + rec[more];
}
cur = cur * mul % m;
}
return -1;
}

1.3 Prime & function

1.3.1 prime filter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int countPrimes(int n) {
bool *vis = new bool[n + 1];
int *prime = new int[n + 1];
memset(vis, 0, n + 1);
int res = 0;
for (int i = 2; i <= n; ++i){
if (!vis[i]){
prime[res++] = i;
}
for (int j = 0; j < res && i * prime[j] <= n; ++j){
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
return res;
}

1.3.2 prime check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool test(int n, int a, int d){
if(n == 2) return true;
if(n == a) return true;
if((n & 1) == 0) return false;
while(!(d & 1)) d >>= 1;
int t = pow_mod(a, d, n);
while((d != n - 1) && (t != 1) && (t != n - 1)){
t = (LL) t * t % n;
d <<= 1;
}
return (t == n - 1 || (d & 1) == 1);
}
bool is_prime(int n){
if(n < 2) return false;
int a[] = {2, 3, 61};
for(int i = 0; i < 2; ++i)
if(!test(n, a[i], n - 1)) return false;
return true;
}

1.3.3 euler function

1
2
3
4
5
6
7
8
9
10
11
12
int euler[MAXN];
void get_euler(){
memset(euler, 0, sizeof(euler));
euler[1] = 1;
for(int i = 2; i <= MAXN; ++i){
if(euler[i]) continue;
for(int j = i; j <= MAXN; j += i){
if(!euler[j]) euler[j] = j;
euler[j] = euler[j] / i * (i - 1);
}
}
}

1.3.4 mobius function

1
2
3
4
5
6
7
8
9
10
11
12
const int n = 1 << 20;
int mu[n];
int get_mobius(){
for(int i = 1; i <= n; ++i){
int target = i == 1 ? 1 : 0;
int delta = target - mu[i];
mu[i] = delta;
for(int j = i << 1; j <= n; j += i){
mu[j] += delta;
}
}
}

1.4 Numerical calculation

1.4.1 numerical integration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<class T>
double romberg(const T &f, double a, double b, double eps = 1e-8){
vector<double> t;
double h = b - a, last, cur;
int k = 1, i = 1;
t.push_back(h * (f(a) + f(b)) / 2);
do{
last = t.back();
cur = 0;
double x + h / 2;
for(int j = 0; j < k; ++j){
cur += f(x);
x += h;
}
cur = (t[0] + h * curr) / 2;
double k1 = 4.0 / 3.0, k2 = 1.0 / 3.0;
for(int j = 0; j < i; ++j){
double temp = k1 * cur - k2 * t[j];
t[j] = cur;
cur = temp;
k2 /= 4 * k1 - k2;
k1 = k2 + 1;
}
t.push_back(cur);
k *= 2;
h /= 2;
++i;
}while(fabs(last - cur) > eps);
return t.back();
}

1.4.2 equation of higher degree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const double eps = 1e-12;
const double inf = 1e+12;
inline int sign(double x){
return x < -eps ? -1 : x > eps;
}
inline double get(const vector<double> &coef, double x){
double e = 1, s = 0;
for(int i = 0; i < coef.size(); ++i){
s += coef[i] * e;
e *= x;
}
return x;
}
double find(const vector<double> &coef, int n, double lo, double hi){
double sign_lo, sign_hi;
if((sign_lo == sign(get(coef, lo))) == 0) return lo;
if((sign_hi = sign(get(coef, hi))) == 0) return hi;
if(sign_lo * sign_hi > 0) return inf;
for(int step = 0; step < 100 && hi - lo > eps; ++step){
double m = (lo + hi) * 0.5;
int sign_mid = sign(get(coef, m));
if(sign_mid == 0) return m;
if(sign_lo * sign_mid < 0){
hi = m;
}
else{
lo = m;
}
}
return (lo + hi) * 0.5;
}
vector<double> equation(vector<double> coef, int n){
vector<double> ret;
if(n == 1){
if(sign(coef[1])) ret.push_back(-coef[0] / coef[1]);
return ret;
}
vector<double> dcoef(n);
for(int i = 0; i < n; ++i){
dcoef[i] = coef[i + 1] * (i + 1);
}
vector<double> droot = solve(dcoef, n - 1);
droot.insert(droot.begin(), -inf);
for(int i = 0; i + 1 < droot.size(); ++i){
double tmp = find(coef, n, droot[i], droot[i + 1]);
if(tmp < inf) ret.push_back(tmp);
}
return ret;
}

1.5 Others

1.5.1 quick pow modulo

1
2
3
4
5
6
7
8
9
LL pow_mod(LL x, LL y, LL mod){
LL res = 1;
while(y){
if(y) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}

1.5.2 numeral system conversion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
string transform(int x, int y, string s){
string res;
int sum = 0;
for(int i = 0; i < s.length(); ++i){
if(s[i] == '-') continue;
if(s[i] >= '0' && s[i] <= '9'){
sum = sum * x + s[i] - '0';
}
else{
sum = sum * x + s[i] - 'A' + 10;
}
}
while(sum){
char tmp = sum % y;
sum /= y;
if(tmp <= 9){
tmp += '0');
}
else{
tmp = tmp - 10 + 'A';
}
res = tmp + res;
}
if(res.length() == 0) res = "0";
if(s[0] == '-') res = '-' + res;
return res;
}

1.5.3 gray code

1
2
3
4
5
6
7
vector<int> gray_gen(int n){
vector<int> res;
for(int i = 0; i < (1 << n); ++i){
res.push_back(i ^ (i >> 1));
}
return res;
}

1.5.4 fast fourier transform

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct Complex{
double re, im;
Complex(double _re = 0., double _im = 0.) :re(_re), im(_im){}
Complex operator*(Complex r) { return Complex(re*r.re - im*r.im, re*r.im + im*r.re); }
Complex operator+(Complex r) { return Complex(re + r.re, im + r.im); }
Complex operator-(Complex r) { return Complex(re - r.re, im - r.im); }
};
void bit_rev(Complex *a, int loglen, int len){
for (int i = 0; i < len; ++i){
int t = i, p = 0;
for (int j = 0; j < loglen; ++j){
p <<= 1;
p = p | (t & 1);
t >>= 1;
}
if (p < i){
Complex temp = a[p];
a[p] = a[i];
a[i] = temp;
}
}
}
void FFT(Complex *a, int loglen, int len, int on){
bit_rev(a, loglen, len);
for (int s = 1, m = 2; s <= loglen; ++s, m <<= 1){
Complex wn = Complex(cos(2 * PI*on / m), sin(2 * PI*on / m));
for (int i = 0; i < len; i += m){
Complex w = Complex(1.0, 0);
for (int j = 0; j < m / 2; ++j){
Complex u = a[i + j];
Complex v = w*a[i + j + m / 2];
a[i + j] = u + v;
a[i + j + m / 2] = u - v;
w = w*wn;
}
}
}
if (on == -1){
for (int i = 0; i < len; ++i) a[i].re /= len, a[i].im /= len;
}
}

1.5.5 fraction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Fraction{
LL num, den;
Fraction(LL num = 0, LL den = 1){
if(den < 0){
num = -num;
den = -den;
}
assert(den != 0);
LL g = gcd(abs(num), den);
this->num = num / g;
this->den = den / g;
}
Fraction operator +(const Fraction &o) const{
return Fraction(num * o.den + den * o.num, den * o.den);
}
Fraction operator -(const Fraction &o) const{
return Fraction(num * o.den - den * o.num, den * o.den);
}
Fraction operator *(const Fraction &o) const{
return Fraction(num * o.num, den * o.den);
}
Fraction operator /(const Fraction &o) const{
return Fraction(num * o.den, den * o.num);
}
Fraction operator <(const Fraction &o) const{
return num * o.den < den * o.num;
}
Fraction operator ==(const Fraction &o) const{
return num * o.den == den * o.num;
}
}

1.5.6 cantor expansion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//POJ1077
int cantor(int a[], int n){
int ans = 0;
for(int i = 1; i <= n; ++i){
temp = a[i] - 1;
for(int j = 1; j < i; ++j)
if(a[j] < a[i]) --temp;
ans += factor[n - i] * temp;
}
return temp;
}
void uncantor(int x, int a[N]){
bool used[N];
memset(used, 0, sizeof(used));
for(int i = 1; i <= n; ++i){
temp = x / factor[n - i];
for(int j = 1; j <= n; ++j){
if(used[j]) continue;
if(temp == 0) break;
--temp;
}
a[i] = j;
used[j] = true;
x %= factor[n - i];
}
}

2. Graph

2.1 Graph travelsal & connectivity

2.1.1 cut point & bridge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cut_bridge(int u, int fa){
int lowu = pre[u] = ++dfs_clock;
int child = 0;
for(int i = 0; i < G[u].size(); ++i){
int v = G[u][i];
if(!pre[v]){
++child;
int lowv = cut_bridge(v, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u]) iscut[u] = true;
}
else if(pre[v] < pre[u] && v != fa){
lowu = min(lowu, pre[v]);
}
}
if(fa < 0 && child == 1) iscut[u] = 0;
low[u] = lowu;
return lowu;
}

2.1.2 biconnected component - point

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct Edge{
int from, to;
Edge(int from = 0, int to = 0) :from(from), to(to){};
};
vector<int> G[MAXN], bcc[MAXN];
int pre[MAXN], iscut[MAXN], bccno[MAXN], pre[MAXN];
stack<Edge> S;
int dfs_clock, bcc_cnt, bridge_cnt;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = 0;
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i];
Edge e = Edge(u, v);
if (!pre[v]){
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (lowv >= pre[u]){
iscut[u] = true;
bcc_cnt++;
bcc[bcc_cnt].clear();
while (true){
Edge x = S.top(); S.pop();
if (bccno[x.from] != bcc_cnt){
bcc[bcc_cnt].push_back(x.from);
bccno[x.from] = bcc_cnt;
}
if (bccno[x.to] != bcc_cnt){
bcc[bcc_cnt].push_back(x.to);
bccno[x.to] = bcc_cnt;
}
if (x.from == u && x.to == v) break;
}
}
}
else if (pre[v] < pre[u] && v != fa){
S.push(e);
lowu = min(lowu, pre[v]);
}
}
if (fa < 0 && child == 1) iscut[u] = false;
return lowu;
}
void find_bcc(int n)
{
memset(pre, 0, sizeof(pre));
memset(iscut, 0, sizeof(iscut));
memset(bccno, 0, sizeof(bccno));
dfs_clock = bcc_cnt = 0;
bridge_cnt = 0;
for (int i = 0; i < n; i++){
if (!pre[i]) dfs(i, -1);
}
}

2.1.3 biconnected component - edge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct Edge{
int from, to;
Edge(int from = 0, int to = 0) :from(from), to(to){};
};
vector<int> G[MAXN], bcc[MAXN];
int pre[MAXN], iscut[MAXN], bccno[MAXN], pre[MAXN];
stack<Edge> S;
int dfs_clock, bcc_cnt, bridge_cnt;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = 0;
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i];
Edge e = Edge(u, v);
if (!pre[v]){
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (lowv >= pre[u]){
iscut[u] = true;
bcc_cnt++;
bcc[bcc_cnt].clear();
while (true){
Edge x = S.top(); S.pop();
if (bccno[x.from] != bcc_cnt){
bcc[bcc_cnt].push_back(x.from);
bccno[x.from] = bcc_cnt;
}
if (bccno[x.to] != bcc_cnt){
bcc[bcc_cnt].push_back(x.to);
bccno[x.to] = bcc_cnt;
}
if (x.from == u && x.to == v) break;
}
}
}
else if (pre[v] < pre[u] && v != fa){
S.push(e);
lowu = min(lowu, pre[v]);
}
}
if (fa < 0 && child == 1) iscut[u] = false;
return lowu;
}
void find_bcc(int n)
{
memset(pre, 0, sizeof(pre));
memset(iscut, 0, sizeof(iscut));
memset(bccno, 0, sizeof(bccno));
dfs_clock = bcc_cnt = 0;
bridge_cnt = 0;
for (int i = 0; i < n; i++){
if (!pre[i]) dfs(i, -1);
}
}

2.1.4 strong connected component

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int pre[MAXN], lowlink[MAXN], sccno[MAXN];
vector<int> G[MAXN];
stack<int> S;
int dfs_clock, scc_cnt;
void dfs(int u){
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if (!pre[v]){
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else{
if (!sccno[v]){
lowlink[u] = min(lowlink[u], pre[v]);
}
}
}
if (lowlink[u] == pre[u]){
scc_cnt++;
for (;;){
int x = S.top();
S.pop();
sccno[x] = scc_cnt;
if (x == u) break;
}
}
}
void find_scc(int n){
dfs_clock = scc_cnt = 0;
memset(sccno, 0, sizeof(sccno));
memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; i++){
if (!pre[i]){
dfs(i);
}
}
}

2.1.5 topo sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int MAXN = 1005;
vector<int> G[MAXN];
int deg[MAXN], n, m;
int ans[MAXN];
bool toposort(){
memset(deg, 0, sizeof(deg));
for(int i = 0; i < n; ++i){
for(int j = 0; j < G[i].size(); ++j){
++deg[G[i][j]];
}
}
int tot = 0;
queue<int> Q;
for(int i = 0; i < n; ++i){
if(!deg[i]) Q.push(i);
}
while(!Q.empty()){
int x = Q.front(); Q.pop();
L[tot++] = x;
for(int j = 0; j < G[x].size(); ++j){
int t = G[x][j];
deg[t]--;
if(!deg[t]) Q.push(t);
}
}
if(tot == n) return true;
return false;
}

2.1.6 Two SAT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
struct TwoSat{
int n;
vector<int> G[MAXN*2];
bool mark[MAXN*2];
int S[MAXN*2], c;
bool dfs(int x){
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x] = true;
S[c++] = x;
for(int i = 0; i < G[x].size(); i++){
if(!dfs(G[x][i])) return false;
}
return true;
}
void init(int n){
this->n = n;
for(int i = 0; i < n * 2; i++){
G[i].clear();
}
memset(mark, 0, sizeof(mark));
}
void add_clause(int x, int xval, int y, int yval){
x = x * 2 + xval;
y = y * 2 + yval;
G[x^1].push_back(y);
G[y^1].push_back(x);
}
bool solve(){
for(int i = 0; i < n * 2; i += 2){
if(!mark[i] && !mark[i + 1]){
c = 0;
if(!dfs(i)){
while(c > 0){
mark[S[--c]] = false;
}
if(!dfs(i + 1)){
return false;
}
}
}
}
return true;
}
};
TwoSat p;
int n, T[MAXN][2];
bool check(int diff){
p.init(n);
for(int i = 0; i < n; i++){
for(int a = 0; a < 2; a++){
for(int j = i + 1; j < n; j++){
for(int b = 0; b < 2; b++){
if(abs(T[i][a] - T[j][b]) < diff){
p.add_clause(i, a^1, j, b^1);
}
}
}
}
}
return p.solve();
}
int main()
{
#ifdef OPEN_FILE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // OPEN_FILE
while(~scanf("%d", &n) && n){
int left = 0, right = 0;
for(int i = 0; i < n; i++){
for(int a = 0; a < 2; a++){
scanf("%d", &T[i][a]);
right = max(right, T[i][a]);
}
}
while(left < right){
int mid = left + (right - left + 1) / 2;
if(check(mid)){
left = mid;
}
else{
right = mid - 1;
}
}
printf("%d\n", left);
}
}

2.2 Graph path

2.2.1 dijstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct Edge
{
int from, to, dist;
Edge(int from, int to, int dist):from(from), to(to), dist(dist){};
};
struct HeapNode
{
int d, u;
HeapNode(int d, int u):d(d), u(u){};
bool operator <(const HeapNode& rhs) const{
return d > rhs.d;
}
};
struct Dijstra
{
int n, m;
vector<Edge> edges;
vector<int> G[MAXN];
bool done[MAXN];
int d[MAXN];
int p[MAXN];
void init(int n){
this->n = n;
for(int i = 0; i <= n; i++){
G[i].clear();
road[i].clear();
}
edges.clear();
}
void AddEdge(int from, int to, int dist){
edges.push_back(Edge(from, to, dist));
m = edges.size();
G[from].push_back(m - 1);
}
void dijstra(int s){
priority_queue<HeapNode> Q;
for(int i = 0; i <= n; i++){
d[i] = INF;
}
d[s] = 0;
memset(done, 0, sizeof(done));
Q.push(HeapNode(0, s));
while(!Q.empty()){
HeapNode x = Q.top();
Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0; i < G[u].size(); i++){
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push(HeapNode(d[e.to], e.to));
}
}
}
}
};

2.2.2 spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int spfa(int s)
{
queue <int> q;
memset(d, INF, sizeof(d));
d[s] = 0;
memset(cnt, 0, sizeof(cnt));
memset(vis, 0, sizeof(vis));
q.push(s);
vis[s] = 1;
while (!q.empty())
{
int x;
x = q.front();
q.pop();
while (no[x]){
x = q.front();
q.pop();
}
vis[x] = 0;
for (int i = 0; i < G[x].size(); i++)
{
int y = G[x][i].v;
if (d[x] + G[x][i].w < d[y])
{
d[y] = d[x] + G[x][i].w;
if (!vis[y])
{
vis[y] = 1;
q.push(y);
}
}
}
}
}

2.2.3 K-th shortest path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool vis[maxn];
int dist[maxn];
struct Node {
int v, c;
Node (int _v = 0, int _c = 0) : v(_v), c(_c) {}
bool operator < (const Node &rhs) const {
return c + dist[v] > rhs.c + dist[rhs.v];
}
};
vector<Edge>E[maxn], revE[maxn];
int astar(int s) {
priority_queue<Node> que;
que.push(Node(s, 0)); k--;
while (!que.empty()) {
Node pre = que.top(); que.pop();
int u = pre.v;
if (u == t) {
if (k) k--;
else return pre.c;
}
for (int i = 0; i < (int)revE[u].size(); i++) {
int v = revE[u][i].v;
int c = revE[u][i].cost;
que.push(Node(v, pre.c + c));
}
}
return -1;
}
void addedge(int u, int v, int w) {
revE[u].push_back(Edge(v, w));
E[v].push_back(Edge(u, w));
}

2.3 Matching

2.3.1 hungarian algorithm

1
2
3
4
5
6
7
8
9
10
11
12
bool dfs(int u){
for(int i = 1; i <= n; i++){
if(a[u][i] && !visit[i]){
visit[i] = true;
if(match[i] == -1 || dfs(match[i])){
match[i] = u;
}
return true;
}r
}
return false;
}

2.3.2 KM algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n, m;
char s[MAXN][MAXM];
int a[MAXN][MAXN], match[MAXN], fx[MAXN], fy[MAXN];
bool x[MAXN], y[MAXN];
bool dfs(int u){
x[u] = true;
for(int i = 1; i <= n; i++){
if(y[i]) continue;
int p = fx[u] + fy[i] - a[u][i];
if(p == 0){
y[i] = true;
if(match[i] == -1 || dfs(match[i])){
match[i] = u;
return true;
}
}else{
m = min(m, p);
}
}
return false;
}
void KM(){
int i,j;
memset(fx,0,sizeof(fx));
memset(fy,0,sizeof(fy));
memset(match,-1,sizeof(match));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(a[i][j] > fx[i]){
fx[i] = a[i][j];
}
}
}
for(int i = 1; i <= n; i++){
while(true){
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
m = INF;
if(dfs(i)) break;
for(int j = 1; j <= n; j++){
if(x[j]) fx[j] -= m;
if(y[j]) fy[j] += m;
}
}
}
}

2.4 Tree

2.4.1 lowest common ancestor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int euler[MAXM], deep[MAXM], pos[MAXN];
int f[20][MAXN];
vector<int>G[MAXN];
bool vis[MAXN];
int top;
int cnt[MAXN];
void dfs(int t, int x)
{
if (pos[x] == -1)
pos[x] = top;
deep[top] = t;
euler[top++] = x;
for (int i = 0; i < G[x].size(); i++)
{
dfs(t + 1, G[x][i]);
deep[top] = t;
euler[top++] = x;
}
}
void rmq(int n)
{
for (int i = 1; i <= n; i++)
f[0][i] = deep[i];
for (int j = 1; j <= (int)(log((double)n) / log(2.0)); j++){
for (int i = 1; i <= n - (1 << j) + 1; i++){
f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
}
}
}
int get(int x, int y)
{
if (x > y){
swap(x, y);
}
int k = (int)(log((double)(y - x + 1.0)) / log(2.0));
int temp = min(f[k][x], f[k][y - (1 << k) + 1]);
for (int i = x; i <= y; i++)
if (deep[i] == temp)
return euler[i];
}

2.4.2 prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int prim() {
memset(vis,0,sizeof(vis));
int i;
int maxedge=0;
for (i = 1; i <= n; i++) {
dis[i]= value[1][i];
}
dis[1] = 0;
vis[1] = true;
for (i = 2; i <= n; i++) {
int temp = inf;
int mark;
for (int j = 1; j <= n; j++) {
if (!vis[j] && dis[j] < temp) {
temp = dis[j];
mark = j;
}
}
if(dis[mark]>maxedge)
maxedge=dis[mark];
vis[mark]=true;
for (int j = 1; j <= n; j++) {
if (!vis[j]&&dis[j]>value[mark][j])
dis[j] = value[mark][j];
}
}
return maxedge;
}

2.4.3 minimum arborescence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
double G[MAXN][MAXN];
int used[MAXN], pass[MAXN], eg[MAXN], more, queue[MAXN];
int n, m;
inline void combine(int id, double &sum){
int tot = 0, from;
for(; id != 0 && !pass[id]; id = eg[id]){
queue[tot++] = id;
pass[id] = 1;
}
for(from = 0; from < tot && queue[from] != id; ++from);
if(from == tot) return;
more = 1;
for(in i = from; i < tot; ++i){
sum += G[eg[queue[i]]][queue[i]];
if(i != from){
used[queue[i]] = 1;
for(int j = 1; j <= n; ++j){
if(!used[j]) continue;
if(G[queue[i]][j] < G[id][j])
G[id][j] = G[queue[i]][j];
}
}
}
for(int i = 1; i <= n; ++i){
if(used[i] || i == id) continue;
for(int j = from; j < tot; ++j){
k = queue[j];
if(G[i][id] > G[i][k] - G[eg[k]][k]){
G[i][id] = G[i][k] - G[eg[k]][k];
}
}
}
}
inline double mdst(int root){
double sum = 0;
memset(used, 0, sizeof(used));
for(more = 1; more;){
more = 0;
memset(eg, 0, sizeof(eg));
for(int i = 1; i <= n; ++i){
for(int j = 1, k = 0; j <= n; ++j){
if(used[j] || j == i) continue;
if(k == 0 || G[j][i] < G[k][i]){
k = j;
}
}
eg[i] = k;
}
for(int i = 1; i <= n; ++i){
if(used[i] || pass[i] || i == root) continue;
combine(i, sum);
}
}
for(int i = 1; i <= n ++i){
if(used[i] || i == root) continue;
sum += G[eg[i]][i];
}
return sum;
}

2.5 Network Flow

2.5.1 dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
int n;
int win[MAXN], remain[MAXN][MAXN];
struct Edge{
int from, to, cap, flow;
//Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){};
};
bool comp(const Edge& a, const Edge& b){
return (a.from < b.from || (a.from == b.from && a.to < b.to));
}
struct Dinic{
int n, m, i, s, t;
Edge e;
vector<Edge> edges;
vector<int> G[MAXN];
int d[MAXN], cur[MAXN];
bool vis[MAXN];
void init(int n){
this->n = n;
for (i = 0; i <= n; i++){
G[i].clear();
}
edges.clear();
}
void AddEdge(int from, int to, int cap){
edges.push_back(Edge{ from, to, cap, 0 });
edges.push_back(Edge{ to, from, 0, 0 });
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS(){
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()){
int x = Q.front();
Q.pop();
for (i = 0; i < G[x].size(); i++){
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow){
vis[e.to] = true;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a){
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++){
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}
int MaxFlow(int s, int t, int need){
int flow = 0;
this->s = s;
this->t = t;
while (BFS()){
memset(cur, 0, sizeof(cur));
flow += DFS(s, INF);
if (flow > need) return flow;
}
return flow;
}
bool checkFull(int s){
for (int i = 0; i < G[s].size(); i++){
if (edges[G[s][i]].flow != edges[G[s][i]].cap){
return false;
}
}
return true;
}
};

2.6 Others

3. Geometry

4. Data Structure

5. Topics

6. Trick