oj.uz

Submission #387889

# Submission time Handle Problem Language Result Execution time Memory
387889 2021-04-09T11:16:26 Z AmShZ Swapping Cities (APIO20_swap) C++11
13 / 100
 987 ms 109812 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 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);
}
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 47560 KB Output is correct
2 Correct 29 ms 47560 KB Output is correct
3 Correct 29 ms 47564 KB Output is correct
4 Correct 28 ms 47712 KB Output is correct
5 Correct 30 ms 48064 KB Output is correct
6 Correct 29 ms 47948 KB Output is correct
7 Correct 30 ms 48004 KB Output is correct
8 Correct 31 ms 48076 KB Output is correct
9 Correct 362 ms 90944 KB Output is correct
10 Correct 486 ms 103012 KB Output is correct
11 Correct 465 ms 101212 KB Output is correct
12 Correct 480 ms 104872 KB Output is correct
13 Correct 402 ms 108040 KB Output is correct
14 Correct 439 ms 89732 KB Output is correct
15 Correct 961 ms 104660 KB Output is correct
16 Correct 970 ms 100272 KB Output is correct
17 Correct 971 ms 109812 KB Output is correct
18 Correct 877 ms 107356 KB Output is correct
19 Correct 200 ms 60624 KB Output is correct
20 Correct 985 ms 104664 KB Output is correct
21 Correct 930 ms 101340 KB Output is correct
22 Correct 987 ms 107096 KB Output is correct
23 Correct 971 ms 107840 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47560 KB Output is correct
2 Correct 29 ms 47560 KB Output is correct
3 Correct 501 ms 96092 KB Output is correct
4 Correct 515 ms 98528 KB Output is correct
5 Correct 509 ms 97000 KB Output is correct
6 Correct 505 ms 98200 KB Output is correct
7 Correct 537 ms 97704 KB Output is correct
8 Correct 494 ms 95792 KB Output is correct
9 Correct 518 ms 97412 KB Output is correct
10 Correct 495 ms 95360 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47560 KB Output is correct
2 Correct 29 ms 47560 KB Output is correct
3 Correct 29 ms 47564 KB Output is correct
4 Correct 28 ms 47712 KB Output is correct
5 Correct 30 ms 48064 KB Output is correct
6 Correct 29 ms 47948 KB Output is correct
7 Correct 30 ms 48004 KB Output is correct
8 Correct 31 ms 48076 KB Output is correct
9 Correct 29 ms 47548 KB Output is correct
10 Correct 30 ms 47924 KB Output is correct
11 Correct 32 ms 48056 KB Output is correct
12 Correct 32 ms 47916 KB Output is correct
13 Correct 30 ms 47948 KB Output is correct
14 Correct 30 ms 47884 KB Output is correct
15 Incorrect 30 ms 48056 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47548 KB Output is correct
2 Correct 29 ms 47560 KB Output is correct
3 Correct 29 ms 47560 KB Output is correct
4 Correct 29 ms 47564 KB Output is correct
5 Correct 28 ms 47712 KB Output is correct
6 Correct 30 ms 48064 KB Output is correct
7 Correct 29 ms 47948 KB Output is correct
8 Correct 30 ms 48004 KB Output is correct
9 Correct 31 ms 48076 KB Output is correct
10 Correct 362 ms 90944 KB Output is correct
11 Correct 486 ms 103012 KB Output is correct
12 Correct 465 ms 101212 KB Output is correct
13 Correct 480 ms 104872 KB Output is correct
14 Correct 402 ms 108040 KB Output is correct
15 Correct 30 ms 47924 KB Output is correct
16 Correct 32 ms 48056 KB Output is correct
17 Correct 32 ms 47916 KB Output is correct
18 Correct 30 ms 47948 KB Output is correct
19 Correct 30 ms 47884 KB Output is correct
20 Incorrect 30 ms 48056 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47560 KB Output is correct
2 Correct 29 ms 47560 KB Output is correct
3 Correct 29 ms 47564 KB Output is correct
4 Correct 28 ms 47712 KB Output is correct
5 Correct 30 ms 48064 KB Output is correct
6 Correct 29 ms 47948 KB Output is correct
7 Correct 30 ms 48004 KB Output is correct
8 Correct 31 ms 48076 KB Output is correct
9 Correct 362 ms 90944 KB Output is correct
10 Correct 486 ms 103012 KB Output is correct
11 Correct 465 ms 101212 KB Output is correct
12 Correct 480 ms 104872 KB Output is correct
13 Correct 402 ms 108040 KB Output is correct
14 Correct 439 ms 89732 KB Output is correct
15 Correct 961 ms 104660 KB Output is correct
16 Correct 970 ms 100272 KB Output is correct
17 Correct 971 ms 109812 KB Output is correct
18 Correct 877 ms 107356 KB Output is correct
19 Correct 501 ms 96092 KB Output is correct
20 Correct 515 ms 98528 KB Output is correct
21 Correct 509 ms 97000 KB Output is correct
22 Correct 505 ms 98200 KB Output is correct
23 Correct 537 ms 97704 KB Output is correct
24 Correct 494 ms 95792 KB Output is correct
25 Correct 518 ms 97412 KB Output is correct
26 Correct 495 ms 95360 KB Output is correct
27 Correct 30 ms 47924 KB Output is correct
28 Correct 32 ms 48056 KB Output is correct
29 Correct 32 ms 47916 KB Output is correct
30 Correct 30 ms 47948 KB Output is correct
31 Correct 30 ms 47884 KB Output is correct
32 Incorrect 30 ms 48056 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47548 KB Output is correct
2 Correct 29 ms 47560 KB Output is correct
3 Correct 29 ms 47560 KB Output is correct
4 Correct 29 ms 47564 KB Output is correct
5 Correct 28 ms 47712 KB Output is correct
6 Correct 30 ms 48064 KB Output is correct
7 Correct 29 ms 47948 KB Output is correct
8 Correct 30 ms 48004 KB Output is correct
9 Correct 31 ms 48076 KB Output is correct
10 Correct 362 ms 90944 KB Output is correct
11 Correct 486 ms 103012 KB Output is correct
12 Correct 465 ms 101212 KB Output is correct
13 Correct 480 ms 104872 KB Output is correct
14 Correct 402 ms 108040 KB Output is correct
15 Correct 439 ms 89732 KB Output is correct
16 Correct 961 ms 104660 KB Output is correct
17 Correct 970 ms 100272 KB Output is correct
18 Correct 971 ms 109812 KB Output is correct
19 Correct 877 ms 107356 KB Output is correct
20 Correct 501 ms 96092 KB Output is correct
21 Correct 515 ms 98528 KB Output is correct
22 Correct 509 ms 97000 KB Output is correct
23 Correct 505 ms 98200 KB Output is correct
24 Correct 537 ms 97704 KB Output is correct
25 Correct 494 ms 95792 KB Output is correct
26 Correct 518 ms 97412 KB Output is correct
27 Correct 495 ms 95360 KB Output is correct
28 Correct 30 ms 47924 KB Output is correct
29 Correct 32 ms 48056 KB Output is correct
30 Correct 32 ms 47916 KB Output is correct
31 Correct 30 ms 47948 KB Output is correct
32 Correct 30 ms 47884 KB Output is correct
33 Incorrect 30 ms 48056 KB Output isn't correct
34 Halted 0 ms 0 KB -