oj.uz

Submission #387904

# Submission time Handle Problem Language Result Execution time Memory
387904 2021-04-09T11:58:20 Z AmShZ Swapping Cities (APIO20_swap) C++11
73 / 100
 2000 ms 139960 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 = 10 + 10;
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 27 ms 47564 KB Output is correct
2 Correct 28 ms 47504 KB Output is correct
3 Correct 27 ms 47448 KB Output is correct
4 Correct 29 ms 47664 KB Output is correct
5 Correct 30 ms 48072 KB Output is correct
6 Correct 30 ms 47940 KB Output is correct
7 Correct 29 ms 48080 KB Output is correct
8 Correct 29 ms 48156 KB Output is correct
9 Correct 423 ms 90892 KB Output is correct
10 Correct 485 ms 102968 KB Output is correct
11 Correct 511 ms 101168 KB Output is correct
12 Correct 517 ms 104828 KB Output is correct
13 Correct 431 ms 108036 KB Output is correct
14 Correct 417 ms 89648 KB Output is correct
15 Correct 1016 ms 104516 KB Output is correct
16 Correct 1084 ms 100200 KB Output is correct
17 Correct 1008 ms 109700 KB Output is correct
18 Correct 1045 ms 107204 KB Output is correct
19 Correct 264 ms 60580 KB Output is correct
20 Correct 1156 ms 104664 KB Output is correct
21 Correct 1147 ms 101300 KB Output is correct
22 Correct 1155 ms 106992 KB Output is correct
23 Correct 1049 ms 107824 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47564 KB Output is correct
2 Correct 28 ms 47504 KB Output is correct
3 Correct 523 ms 96112 KB Output is correct
4 Correct 535 ms 98524 KB Output is correct
5 Correct 501 ms 96976 KB Output is correct
6 Correct 563 ms 98344 KB Output is correct
7 Correct 517 ms 97848 KB Output is correct
8 Correct 504 ms 95684 KB Output is correct
9 Correct 513 ms 97380 KB Output is correct
10 Correct 532 ms 95328 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47564 KB Output is correct
2 Correct 28 ms 47504 KB Output is correct
3 Correct 27 ms 47448 KB Output is correct
4 Correct 29 ms 47664 KB Output is correct
5 Correct 30 ms 48072 KB Output is correct
6 Correct 30 ms 47940 KB Output is correct
7 Correct 29 ms 48080 KB Output is correct
8 Correct 29 ms 48156 KB Output is correct
9 Correct 28 ms 47500 KB Output is correct
10 Correct 30 ms 48000 KB Output is correct
11 Correct 30 ms 48024 KB Output is correct
12 Correct 29 ms 47948 KB Output is correct
13 Correct 34 ms 47960 KB Output is correct
14 Correct 29 ms 47876 KB Output is correct
15 Correct 29 ms 48068 KB Output is correct
16 Correct 30 ms 48104 KB Output is correct
17 Correct 30 ms 48124 KB Output is correct
18 Correct 29 ms 47948 KB Output is correct
19 Correct 29 ms 47976 KB Output is correct
20 Correct 29 ms 48060 KB Output is correct
21 Correct 30 ms 48144 KB Output is correct
22 Correct 33 ms 48212 KB Output is correct
23 Correct 30 ms 47848 KB Output is correct
24 Correct 31 ms 48284 KB Output is correct
25 Correct 33 ms 48352 KB Output is correct
26 Correct 31 ms 48356 KB Output is correct
27 Correct 30 ms 48064 KB Output is correct
28 Correct 33 ms 48304 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47500 KB Output is correct
2 Correct 27 ms 47564 KB Output is correct
3 Correct 28 ms 47504 KB Output is correct
4 Correct 27 ms 47448 KB Output is correct
5 Correct 29 ms 47664 KB Output is correct
6 Correct 30 ms 48072 KB Output is correct
7 Correct 30 ms 47940 KB Output is correct
8 Correct 29 ms 48080 KB Output is correct
9 Correct 29 ms 48156 KB Output is correct
10 Correct 423 ms 90892 KB Output is correct
11 Correct 485 ms 102968 KB Output is correct
12 Correct 511 ms 101168 KB Output is correct
13 Correct 517 ms 104828 KB Output is correct
14 Correct 431 ms 108036 KB Output is correct
15 Correct 30 ms 48000 KB Output is correct
16 Correct 30 ms 48024 KB Output is correct
17 Correct 29 ms 47948 KB Output is correct
18 Correct 34 ms 47960 KB Output is correct
19 Correct 29 ms 47876 KB Output is correct
20 Correct 29 ms 48068 KB Output is correct
21 Correct 30 ms 48104 KB Output is correct
22 Correct 30 ms 48124 KB Output is correct
23 Correct 29 ms 47948 KB Output is correct
24 Correct 29 ms 47976 KB Output is correct
25 Correct 29 ms 48060 KB Output is correct
26 Correct 30 ms 48144 KB Output is correct
27 Correct 33 ms 48212 KB Output is correct
28 Correct 30 ms 47848 KB Output is correct
29 Correct 31 ms 48284 KB Output is correct
30 Correct 33 ms 48352 KB Output is correct
31 Correct 31 ms 48356 KB Output is correct
32 Correct 30 ms 48064 KB Output is correct
33 Correct 33 ms 48304 KB Output is correct
34 Correct 60 ms 53900 KB Output is correct
35 Correct 507 ms 103988 KB Output is correct
36 Correct 544 ms 99352 KB Output is correct
37 Correct 488 ms 95804 KB Output is correct
38 Correct 479 ms 94356 KB Output is correct
39 Correct 454 ms 93496 KB Output is correct
40 Correct 442 ms 89736 KB Output is correct
41 Correct 540 ms 100820 KB Output is correct
42 Correct 564 ms 102668 KB Output is correct
43 Correct 452 ms 105044 KB Output is correct
44 Correct 512 ms 94728 KB Output is correct
45 Correct 1043 ms 124412 KB Output is correct
46 Correct 588 ms 97588 KB Output is correct
47 Correct 497 ms 94600 KB Output is correct
48 Correct 602 ms 100808 KB Output is correct
49 Correct 855 ms 113212 KB Output is correct
50 Correct 801 ms 108060 KB Output is correct
51 Correct 880 ms 113256 KB Output is correct
52 Correct 1135 ms 119428 KB Output is correct
53 Correct 1134 ms 131460 KB Output is correct
54 Correct 1605 ms 127468 KB Output is correct
55 Correct 499 ms 107360 KB Output is correct
56 Correct 1206 ms 134580 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47564 KB Output is correct
2 Correct 28 ms 47504 KB Output is correct
3 Correct 27 ms 47448 KB Output is correct
4 Correct 29 ms 47664 KB Output is correct
5 Correct 30 ms 48072 KB Output is correct
6 Correct 30 ms 47940 KB Output is correct
7 Correct 29 ms 48080 KB Output is correct
8 Correct 29 ms 48156 KB Output is correct
9 Correct 423 ms 90892 KB Output is correct
10 Correct 485 ms 102968 KB Output is correct
11 Correct 511 ms 101168 KB Output is correct
12 Correct 517 ms 104828 KB Output is correct
13 Correct 431 ms 108036 KB Output is correct
14 Correct 417 ms 89648 KB Output is correct
15 Correct 1016 ms 104516 KB Output is correct
16 Correct 1084 ms 100200 KB Output is correct
17 Correct 1008 ms 109700 KB Output is correct
18 Correct 1045 ms 107204 KB Output is correct
19 Correct 523 ms 96112 KB Output is correct
20 Correct 535 ms 98524 KB Output is correct
21 Correct 501 ms 96976 KB Output is correct
22 Correct 563 ms 98344 KB Output is correct
23 Correct 517 ms 97848 KB Output is correct
24 Correct 504 ms 95684 KB Output is correct
25 Correct 513 ms 97380 KB Output is correct
26 Correct 532 ms 95328 KB Output is correct
27 Correct 30 ms 48000 KB Output is correct
28 Correct 30 ms 48024 KB Output is correct
29 Correct 29 ms 47948 KB Output is correct
30 Correct 34 ms 47960 KB Output is correct
31 Correct 29 ms 47876 KB Output is correct
32 Correct 29 ms 48068 KB Output is correct
33 Correct 30 ms 48104 KB Output is correct
34 Correct 30 ms 48124 KB Output is correct
35 Correct 29 ms 47948 KB Output is correct
36 Correct 60 ms 53900 KB Output is correct
37 Correct 507 ms 103988 KB Output is correct
38 Correct 544 ms 99352 KB Output is correct
39 Correct 488 ms 95804 KB Output is correct
40 Correct 479 ms 94356 KB Output is correct
41 Correct 454 ms 93496 KB Output is correct
42 Correct 442 ms 89736 KB Output is correct
43 Correct 540 ms 100820 KB Output is correct
44 Correct 564 ms 102668 KB Output is correct
45 Correct 452 ms 105044 KB Output is correct
46 Correct 512 ms 94728 KB Output is correct
47 Correct 80 ms 53688 KB Output is correct
48 Correct 1092 ms 103236 KB Output is correct
49 Correct 1151 ms 100480 KB Output is correct
50 Correct 1048 ms 98416 KB Output is correct
51 Correct 1063 ms 97452 KB Output is correct
52 Correct 931 ms 94000 KB Output is correct
53 Correct 621 ms 82348 KB Output is correct
54 Correct 1078 ms 102360 KB Output is correct
55 Correct 1123 ms 104040 KB Output is correct
56 Correct 986 ms 108704 KB Output is correct
57 Correct 894 ms 98012 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47500 KB Output is correct
2 Correct 27 ms 47564 KB Output is correct
3 Correct 28 ms 47504 KB Output is correct
4 Correct 27 ms 47448 KB Output is correct
5 Correct 29 ms 47664 KB Output is correct
6 Correct 30 ms 48072 KB Output is correct
7 Correct 30 ms 47940 KB Output is correct
8 Correct 29 ms 48080 KB Output is correct
9 Correct 29 ms 48156 KB Output is correct
10 Correct 423 ms 90892 KB Output is correct
11 Correct 485 ms 102968 KB Output is correct
12 Correct 511 ms 101168 KB Output is correct
13 Correct 517 ms 104828 KB Output is correct
14 Correct 431 ms 108036 KB Output is correct
15 Correct 417 ms 89648 KB Output is correct
16 Correct 1016 ms 104516 KB Output is correct
17 Correct 1084 ms 100200 KB Output is correct
18 Correct 1008 ms 109700 KB Output is correct
19 Correct 1045 ms 107204 KB Output is correct
20 Correct 523 ms 96112 KB Output is correct
21 Correct 535 ms 98524 KB Output is correct
22 Correct 501 ms 96976 KB Output is correct
23 Correct 563 ms 98344 KB Output is correct
24 Correct 517 ms 97848 KB Output is correct
25 Correct 504 ms 95684 KB Output is correct
26 Correct 513 ms 97380 KB Output is correct
27 Correct 532 ms 95328 KB Output is correct
28 Correct 30 ms 48000 KB Output is correct
29 Correct 30 ms 48024 KB Output is correct
30 Correct 29 ms 47948 KB Output is correct
31 Correct 34 ms 47960 KB Output is correct
32 Correct 29 ms 47876 KB Output is correct
33 Correct 29 ms 48068 KB Output is correct
34 Correct 30 ms 48104 KB Output is correct
35 Correct 30 ms 48124 KB Output is correct
36 Correct 29 ms 47948 KB Output is correct
37 Correct 60 ms 53900 KB Output is correct
38 Correct 507 ms 103988 KB Output is correct
39 Correct 544 ms 99352 KB Output is correct
40 Correct 488 ms 95804 KB Output is correct
41 Correct 479 ms 94356 KB Output is correct
42 Correct 454 ms 93496 KB Output is correct
43 Correct 442 ms 89736 KB Output is correct
44 Correct 540 ms 100820 KB Output is correct
45 Correct 564 ms 102668 KB Output is correct
46 Correct 452 ms 105044 KB Output is correct
47 Correct 512 ms 94728 KB Output is correct
48 Correct 80 ms 53688 KB Output is correct
49 Correct 1092 ms 103236 KB Output is correct
50 Correct 1151 ms 100480 KB Output is correct
51 Correct 1048 ms 98416 KB Output is correct
52 Correct 1063 ms 97452 KB Output is correct
53 Correct 931 ms 94000 KB Output is correct
54 Correct 621 ms 82348 KB Output is correct
55 Correct 1078 ms 102360 KB Output is correct
56 Correct 1123 ms 104040 KB Output is correct
57 Correct 986 ms 108704 KB Output is correct
58 Correct 894 ms 98012 KB Output is correct
59 Correct 264 ms 60580 KB Output is correct
60 Correct 1156 ms 104664 KB Output is correct
61 Correct 1147 ms 101300 KB Output is correct
62 Correct 1155 ms 106992 KB Output is correct
63 Correct 1049 ms 107824 KB Output is correct
64 Correct 29 ms 47976 KB Output is correct
65 Correct 29 ms 48060 KB Output is correct
66 Correct 30 ms 48144 KB Output is correct
67 Correct 33 ms 48212 KB Output is correct
68 Correct 30 ms 47848 KB Output is correct
69 Correct 31 ms 48284 KB Output is correct
70 Correct 33 ms 48352 KB Output is correct
71 Correct 31 ms 48356 KB Output is correct
72 Correct 30 ms 48064 KB Output is correct
73 Correct 33 ms 48304 KB Output is correct
74 Correct 1043 ms 124412 KB Output is correct
75 Correct 588 ms 97588 KB Output is correct
76 Correct 497 ms 94600 KB Output is correct
77 Correct 602 ms 100808 KB Output is correct
78 Correct 855 ms 113212 KB Output is correct
79 Correct 801 ms 108060 KB Output is correct
80 Correct 880 ms 113256 KB Output is correct
81 Correct 1135 ms 119428 KB Output is correct
82 Correct 1134 ms 131460 KB Output is correct
83 Correct 1605 ms 127468 KB Output is correct
84 Correct 499 ms 107360 KB Output is correct
85 Correct 1206 ms 134580 KB Output is correct
86 Correct 350 ms 75116 KB Output is correct
87 Correct 1099 ms 103776 KB Output is correct
88 Correct 1161 ms 104104 KB Output is correct
89 Correct 933 ms 105172 KB Output is correct
90 Correct 1164 ms 125020 KB Output is correct
91 Correct 1196 ms 130140 KB Output is correct
92 Correct 1101 ms 117108 KB Output is correct
93 Correct 1698 ms 126124 KB Output is correct
94 Correct 1441 ms 139960 KB Output is correct
95 Execution timed out 2091 ms 136572 KB Time limit exceeded
96 Halted 0 ms 0 KB -