oj.uz

Submission #387906

# Submission time Handle Problem Language Result Execution time Memory
387906 2021-04-09T12:00:19 Z AmShZ Swapping Cities (APIO20_swap) C++11
100 / 100
 1825 ms 132180 KB 
// khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <ll, ll>                                    pll;
typedef pair <pll,  ll>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 2e5 + 10;
const int xm = 18;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int dsu[xn], sz[xn], par[xm][xn];
int H[xn], mn[xn], a[xn], wp[xn];
pii mx[xm][xn];
bool inmst[xn];
set <pii> st[xn], ts[xn], S[xn], T[xn];
vector <pip> E;
vector <pii> adj[xn], G[xn], vec;

int get_root(int v){
	if (v == dsu[v])
		return v;
	return dsu[v] = get_root(dsu[v]);
}
void preDFS(int v){
	for (int i = 1; i < xm; ++ i){
		par[i][v] = par[i - 1][par[i - 1][v]];
		mx[i][v].A = max(mx[i - 1][v].A, mx[i - 1][par[i - 1][v]].A);
		mx[i][v].B = min(mx[i - 1][v].B, mx[i - 1][par[i - 1][v]].B);
	}
	vec.clear();
	for (pii u : adj[v])
		if (u.A != par[0][v])
			vec.push_back({E[u.B].A, u.A}), S[v].insert({E[u.B].A, u.A});
	sort(all(vec));
	for (int i = 1; i < SZ(vec); ++ i)
		mx[0][vec[i].B].B = min(mn[v], vec[0].A);
	if (SZ(vec))
		mx[0][vec[0].B].B = mn[v];
	if (SZ(vec) > 1)
		mx[0][vec[0].B].B = min(mn[v], vec[1].A);
	a[v] = inf;
	int ted = 0;
	for (pii x : T[v]){
		++ ted;
		if (ted == 3){
			a[v] = x.A;
			break;
		}
	}
	for (pii u : adj[v]){
		if (u.A == par[0][v])
			continue;
		par[0][u.A] = v;
		mx[0][u.A].A = E[u.B].A;
		H[u.A] = H[v] + 1;
		wp[u.A] = E[u.B].A;
		preDFS(u.A);
		a[v] = min(a[v], max(a[u.A], E[u.B].A));
	}
}
int LCA(int v, int u){
	if (H[v] > H[u])
		swap(v, u);
	for (int i = xm - 1; i >= 0; -- i)
		if ((1 << i) <= H[u] - H[v])
			u = par[i][u];
	if (v == u)
		return v;
	for (int i = xm - 1; i >= 0; -- i)
		if (par[i][v] != par[i][u])
			v = par[i][v], u = par[i][u];
	return par[0][v];
}
void merge(int v, int u){
	v = get_root(v);
	u = get_root(u);
	if (sz[v] < sz[u])
		swap(v, u);
	dsu[u] = v, sz[v] += sz[u];
	for (pii x : st[u])
		st[v].insert(x);
}
void DFS(int v){
	for (pii u : adj[v])
		if (u.A != par[0][v])
			DFS(u.A), merge(v, u.A);
	int rt = get_root(v);
	for (pii u : G[v]){
		int lca = LCA(v, u.A);
		st[rt].insert({E[u.B].A, u.B});
		ts[lca].insert({E[u.B].A, u.B});
	}
	for (pii x : ts[v])
		st[rt].erase(x);
	if (SZ(st[rt]))
		a[v] = min(a[v], st[rt].begin() -> A);
}
void DFS2(int v){
	for (pii u : adj[v])
		if (u.A != par[0][v])
			a[u.A] = min(a[u.A], max(a[v], E[u.B].A)), DFS2(u.A);
}
void init(int n, int m, vector <int> V, vector <int> U, vector <int> W){
	for (int i = 1; i <= n; ++ i)
		dsu[i] = i, sz[i] = 1;
	for (int i = 0; i < m; ++ i){
		int v = V[i] + 1, u = U[i] + 1, w = W[i];
		E.push_back({w, {v, u}});
	}
	sort(all(E));
	for (int i = 0; i < m; ++ i){
		pip e = E[i];
		int v = e.B.A, u = e.B.B, w = e.A;
		int pv = v, pu = u;
		T[v].insert({w, u});
		T[u].insert({w, v});
		v = get_root(v);
		u = get_root(u);
		if (v == u){
			G[pv].push_back({pu, i});
			G[pu].push_back({pv, i});
			continue;
		}
		if (sz[v] < sz[u])
			swap(v, u);
		inmst[i] = true;
		dsu[u] = v, sz[v] += sz[u];
		adj[pv].push_back({pu, i});
		adj[pu].push_back({pv, i});
	}
	for (int i = 1; i <= n; ++ i){
		dsu[i] = i, sz[i] = 1;
		mn[i] = inf;
		for (pii u : G[i])
			mn[i] = min(mn[i], E[u.B].A);
	}
	preDFS(1), DFS(1), DFS2(1);
}
int getMinimumFuelCapacity(int v, int u){
	++ v, ++ u;
	int lca = LCA(v, u), res = inf, ans = 0;
	int pv = v, pu = u;
	if (H[v] > H[u])
		swap(v, u);
	for (int i = xm - 1; i >= 0; -- i){
		if (H[u] - H[v] < (1 << i))
			continue;
		if (H[u] - H[v] == (1 << i) && v == lca)
			continue;
		ans = max(ans, mx[i][u].A);
		res = min(res, mx[i][u].B);
		u = par[i][u];
	}
	if (v == lca){
		ans = max(ans, mx[0][u].A);
		res = min(res, mn[lca]);
		u = v;
	}
	for (int i = xm - 1; i >= 0; -- i){
		if (par[i][v] == par[i][u])
			continue;
		ans = max(ans, mx[i][v].A);
		res = min(res, mx[i][v].B);
		ans = max(ans, mx[i][u].A);
		res = min(res, mx[i][u].B);
		v = par[i][v], u = par[i][u];
	}
	if (v != u){
		ans = max(ans, mx[0][v].A);
		ans = max(ans, mx[0][u].A);
		res = min(res, mn[lca]);
		for (pii x : S[lca]){
			if (x.B != v && x.B != u){
				res = min(res, x.A);
				break;
			}
		}
		if (lca - 1)
			res = min(res, wp[lca]);
	}
	v = pv, u = pu;
	res = min(res, min(a[v], a[u]));
	if (res == inf)
		return - 1;
	return max(ans, res);
}


/*
int n, m, q;
vector <int> V, U, W;

int main(){
	InTheNameOfGod;

	cin >> n >> m;
	for (int i = 0; i < m; ++ i){
		int v, u, w;
		cin >> v >> u >> w;
		V.push_back(v);
		U.push_back(u);
		W.push_back(w);
	}
	init(n, m, V, U, W);
	cin >> q;
	while (q --){
		int v, u;
		cin >> v >> u;
		cout << getMinimumFuelCapacity(v, u) << endl;
	}
		
	return 0;
}
5 6
0 1 4
0 2 4
1 4 10
1 3 2
1 2 1
2 3 3
3
1 2
2 4
0 1
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47436 KB Output is correct
2 Correct 28 ms 47456 KB Output is correct
3 Correct 31 ms 47456 KB Output is correct
4 Correct 33 ms 47684 KB Output is correct
5 Correct 33 ms 47940 KB Output is correct
6 Correct 29 ms 47924 KB Output is correct
7 Correct 29 ms 48016 KB Output is correct
8 Correct 30 ms 48096 KB Output is correct
9 Correct 393 ms 89068 KB Output is correct
10 Correct 514 ms 100724 KB Output is correct
11 Correct 459 ms 99020 KB Output is correct
12 Correct 528 ms 102456 KB Output is correct
13 Correct 408 ms 105648 KB Output is correct
14 Correct 441 ms 87856 KB Output is correct
15 Correct 943 ms 102228 KB Output is correct
16 Correct 942 ms 98048 KB Output is correct
17 Correct 908 ms 107312 KB Output is correct
18 Correct 870 ms 104876 KB Output is correct
19 Correct 189 ms 60096 KB Output is correct
20 Correct 959 ms 102420 KB Output is correct
21 Correct 893 ms 99096 KB Output is correct
22 Correct 1016 ms 104636 KB Output is correct
23 Correct 892 ms 105448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47436 KB Output is correct
2 Correct 28 ms 47456 KB Output is correct
3 Correct 483 ms 93856 KB Output is correct
4 Correct 511 ms 96108 KB Output is correct
5 Correct 505 ms 94732 KB Output is correct
6 Correct 494 ms 95892 KB Output is correct
7 Correct 485 ms 95432 KB Output is correct
8 Correct 500 ms 93476 KB Output is correct
9 Correct 483 ms 95160 KB Output is correct
10 Correct 495 ms 93040 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47436 KB Output is correct
2 Correct 28 ms 47456 KB Output is correct
3 Correct 31 ms 47456 KB Output is correct
4 Correct 33 ms 47684 KB Output is correct
5 Correct 33 ms 47940 KB Output is correct
6 Correct 29 ms 47924 KB Output is correct
7 Correct 29 ms 48016 KB Output is correct
8 Correct 30 ms 48096 KB Output is correct
9 Correct 28 ms 47436 KB Output is correct
10 Correct 29 ms 47924 KB Output is correct
11 Correct 30 ms 48036 KB Output is correct
12 Correct 30 ms 47948 KB Output is correct
13 Correct 30 ms 47820 KB Output is correct
14 Correct 29 ms 47812 KB Output is correct
15 Correct 30 ms 47912 KB Output is correct
16 Correct 29 ms 47948 KB Output is correct
17 Correct 28 ms 47972 KB Output is correct
18 Correct 29 ms 48000 KB Output is correct
19 Correct 30 ms 48000 KB Output is correct
20 Correct 29 ms 47948 KB Output is correct
21 Correct 29 ms 48028 KB Output is correct
22 Correct 32 ms 48076 KB Output is correct
23 Correct 30 ms 47884 KB Output is correct
24 Correct 32 ms 48284 KB Output is correct
25 Correct 34 ms 48284 KB Output is correct
26 Correct 33 ms 48204 KB Output is correct
27 Correct 29 ms 48020 KB Output is correct
28 Correct 33 ms 48372 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47436 KB Output is correct
2 Correct 29 ms 47436 KB Output is correct
3 Correct 28 ms 47456 KB Output is correct
4 Correct 31 ms 47456 KB Output is correct
5 Correct 33 ms 47684 KB Output is correct
6 Correct 33 ms 47940 KB Output is correct
7 Correct 29 ms 47924 KB Output is correct
8 Correct 29 ms 48016 KB Output is correct
9 Correct 30 ms 48096 KB Output is correct
10 Correct 393 ms 89068 KB Output is correct
11 Correct 514 ms 100724 KB Output is correct
12 Correct 459 ms 99020 KB Output is correct
13 Correct 528 ms 102456 KB Output is correct
14 Correct 408 ms 105648 KB Output is correct
15 Correct 29 ms 47924 KB Output is correct
16 Correct 30 ms 48036 KB Output is correct
17 Correct 30 ms 47948 KB Output is correct
18 Correct 30 ms 47820 KB Output is correct
19 Correct 29 ms 47812 KB Output is correct
20 Correct 30 ms 47912 KB Output is correct
21 Correct 29 ms 47948 KB Output is correct
22 Correct 28 ms 47972 KB Output is correct
23 Correct 29 ms 48000 KB Output is correct
24 Correct 30 ms 48000 KB Output is correct
25 Correct 29 ms 47948 KB Output is correct
26 Correct 29 ms 48028 KB Output is correct
27 Correct 32 ms 48076 KB Output is correct
28 Correct 30 ms 47884 KB Output is correct
29 Correct 32 ms 48284 KB Output is correct
30 Correct 34 ms 48284 KB Output is correct
31 Correct 33 ms 48204 KB Output is correct
32 Correct 29 ms 48020 KB Output is correct
33 Correct 33 ms 48372 KB Output is correct
34 Correct 64 ms 53620 KB Output is correct
35 Correct 493 ms 101504 KB Output is correct
36 Correct 536 ms 96952 KB Output is correct
37 Correct 473 ms 93648 KB Output is correct
38 Correct 450 ms 92052 KB Output is correct
39 Correct 477 ms 91104 KB Output is correct
40 Correct 392 ms 87732 KB Output is correct
41 Correct 505 ms 98172 KB Output is correct
42 Correct 492 ms 100356 KB Output is correct
43 Correct 434 ms 102576 KB Output is correct
44 Correct 440 ms 92348 KB Output is correct
45 Correct 939 ms 122520 KB Output is correct
46 Correct 489 ms 95064 KB Output is correct
47 Correct 472 ms 92236 KB Output is correct
48 Correct 557 ms 98488 KB Output is correct
49 Correct 788 ms 112988 KB Output is correct
50 Correct 705 ms 107832 KB Output is correct
51 Correct 794 ms 111680 KB Output is correct
52 Correct 1033 ms 117216 KB Output is correct
53 Correct 1004 ms 129120 KB Output is correct
54 Correct 1447 ms 125136 KB Output is correct
55 Correct 427 ms 105140 KB Output is correct
56 Correct 1108 ms 132180 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47436 KB Output is correct
2 Correct 28 ms 47456 KB Output is correct
3 Correct 31 ms 47456 KB Output is correct
4 Correct 33 ms 47684 KB Output is correct
5 Correct 33 ms 47940 KB Output is correct
6 Correct 29 ms 47924 KB Output is correct
7 Correct 29 ms 48016 KB Output is correct
8 Correct 30 ms 48096 KB Output is correct
9 Correct 393 ms 89068 KB Output is correct
10 Correct 514 ms 100724 KB Output is correct
11 Correct 459 ms 99020 KB Output is correct
12 Correct 528 ms 102456 KB Output is correct
13 Correct 408 ms 105648 KB Output is correct
14 Correct 441 ms 87856 KB Output is correct
15 Correct 943 ms 102228 KB Output is correct
16 Correct 942 ms 98048 KB Output is correct
17 Correct 908 ms 107312 KB Output is correct
18 Correct 870 ms 104876 KB Output is correct
19 Correct 483 ms 93856 KB Output is correct
20 Correct 511 ms 96108 KB Output is correct
21 Correct 505 ms 94732 KB Output is correct
22 Correct 494 ms 95892 KB Output is correct
23 Correct 485 ms 95432 KB Output is correct
24 Correct 500 ms 93476 KB Output is correct
25 Correct 483 ms 95160 KB Output is correct
26 Correct 495 ms 93040 KB Output is correct
27 Correct 29 ms 47924 KB Output is correct
28 Correct 30 ms 48036 KB Output is correct
29 Correct 30 ms 47948 KB Output is correct
30 Correct 30 ms 47820 KB Output is correct
31 Correct 29 ms 47812 KB Output is correct
32 Correct 30 ms 47912 KB Output is correct
33 Correct 29 ms 47948 KB Output is correct
34 Correct 28 ms 47972 KB Output is correct
35 Correct 29 ms 48000 KB Output is correct
36 Correct 64 ms 53620 KB Output is correct
37 Correct 493 ms 101504 KB Output is correct
38 Correct 536 ms 96952 KB Output is correct
39 Correct 473 ms 93648 KB Output is correct
40 Correct 450 ms 92052 KB Output is correct
41 Correct 477 ms 91104 KB Output is correct
42 Correct 392 ms 87732 KB Output is correct
43 Correct 505 ms 98172 KB Output is correct
44 Correct 492 ms 100356 KB Output is correct
45 Correct 434 ms 102576 KB Output is correct
46 Correct 440 ms 92348 KB Output is correct
47 Correct 70 ms 53368 KB Output is correct
48 Correct 1022 ms 100788 KB Output is correct
49 Correct 985 ms 97876 KB Output is correct
50 Correct 979 ms 96020 KB Output is correct
51 Correct 924 ms 95160 KB Output is correct
52 Correct 814 ms 91692 KB Output is correct
53 Correct 544 ms 80700 KB Output is correct
54 Correct 989 ms 99992 KB Output is correct
55 Correct 935 ms 101676 KB Output is correct
56 Correct 841 ms 106272 KB Output is correct
57 Correct 799 ms 95548 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47436 KB Output is correct
2 Correct 29 ms 47436 KB Output is correct
3 Correct 28 ms 47456 KB Output is correct
4 Correct 31 ms 47456 KB Output is correct
5 Correct 33 ms 47684 KB Output is correct
6 Correct 33 ms 47940 KB Output is correct
7 Correct 29 ms 47924 KB Output is correct
8 Correct 29 ms 48016 KB Output is correct
9 Correct 30 ms 48096 KB Output is correct
10 Correct 393 ms 89068 KB Output is correct
11 Correct 514 ms 100724 KB Output is correct
12 Correct 459 ms 99020 KB Output is correct
13 Correct 528 ms 102456 KB Output is correct
14 Correct 408 ms 105648 KB Output is correct
15 Correct 441 ms 87856 KB Output is correct
16 Correct 943 ms 102228 KB Output is correct
17 Correct 942 ms 98048 KB Output is correct
18 Correct 908 ms 107312 KB Output is correct
19 Correct 870 ms 104876 KB Output is correct
20 Correct 483 ms 93856 KB Output is correct
21 Correct 511 ms 96108 KB Output is correct
22 Correct 505 ms 94732 KB Output is correct
23 Correct 494 ms 95892 KB Output is correct
24 Correct 485 ms 95432 KB Output is correct
25 Correct 500 ms 93476 KB Output is correct
26 Correct 483 ms 95160 KB Output is correct
27 Correct 495 ms 93040 KB Output is correct
28 Correct 29 ms 47924 KB Output is correct
29 Correct 30 ms 48036 KB Output is correct
30 Correct 30 ms 47948 KB Output is correct
31 Correct 30 ms 47820 KB Output is correct
32 Correct 29 ms 47812 KB Output is correct
33 Correct 30 ms 47912 KB Output is correct
34 Correct 29 ms 47948 KB Output is correct
35 Correct 28 ms 47972 KB Output is correct
36 Correct 29 ms 48000 KB Output is correct
37 Correct 64 ms 53620 KB Output is correct
38 Correct 493 ms 101504 KB Output is correct
39 Correct 536 ms 96952 KB Output is correct
40 Correct 473 ms 93648 KB Output is correct
41 Correct 450 ms 92052 KB Output is correct
42 Correct 477 ms 91104 KB Output is correct
43 Correct 392 ms 87732 KB Output is correct
44 Correct 505 ms 98172 KB Output is correct
45 Correct 492 ms 100356 KB Output is correct
46 Correct 434 ms 102576 KB Output is correct
47 Correct 440 ms 92348 KB Output is correct
48 Correct 70 ms 53368 KB Output is correct
49 Correct 1022 ms 100788 KB Output is correct
50 Correct 985 ms 97876 KB Output is correct
51 Correct 979 ms 96020 KB Output is correct
52 Correct 924 ms 95160 KB Output is correct
53 Correct 814 ms 91692 KB Output is correct
54 Correct 544 ms 80700 KB Output is correct
55 Correct 989 ms 99992 KB Output is correct
56 Correct 935 ms 101676 KB Output is correct
57 Correct 841 ms 106272 KB Output is correct
58 Correct 799 ms 95548 KB Output is correct
59 Correct 189 ms 60096 KB Output is correct
60 Correct 959 ms 102420 KB Output is correct
61 Correct 893 ms 99096 KB Output is correct
62 Correct 1016 ms 104636 KB Output is correct
63 Correct 892 ms 105448 KB Output is correct
64 Correct 30 ms 48000 KB Output is correct
65 Correct 29 ms 47948 KB Output is correct
66 Correct 29 ms 48028 KB Output is correct
67 Correct 32 ms 48076 KB Output is correct
68 Correct 30 ms 47884 KB Output is correct
69 Correct 32 ms 48284 KB Output is correct
70 Correct 34 ms 48284 KB Output is correct
71 Correct 33 ms 48204 KB Output is correct
72 Correct 29 ms 48020 KB Output is correct
73 Correct 33 ms 48372 KB Output is correct
74 Correct 939 ms 122520 KB Output is correct
75 Correct 489 ms 95064 KB Output is correct
76 Correct 472 ms 92236 KB Output is correct
77 Correct 557 ms 98488 KB Output is correct
78 Correct 788 ms 112988 KB Output is correct
79 Correct 705 ms 107832 KB Output is correct
80 Correct 794 ms 111680 KB Output is correct
81 Correct 1033 ms 117216 KB Output is correct
82 Correct 1004 ms 129120 KB Output is correct
83 Correct 1447 ms 125136 KB Output is correct
84 Correct 427 ms 105140 KB Output is correct
85 Correct 1108 ms 132180 KB Output is correct
86 Correct 283 ms 72744 KB Output is correct
87 Correct 927 ms 97280 KB Output is correct
88 Correct 961 ms 97604 KB Output is correct
89 Correct 767 ms 98676 KB Output is correct
90 Correct 1038 ms 120240 KB Output is correct
91 Correct 1060 ms 125040 KB Output is correct
92 Correct 961 ms 110692 KB Output is correct
93 Correct 1481 ms 118072 KB Output is correct
94 Correct 1375 ms 131488 KB Output is correct
95 Correct 1825 ms 127888 KB Output is correct
96 Correct 878 ms 106832 KB Output is correct
97 Correct 1070 ms 121076 KB Output is correct