oj.uz

Submission #387888

# Submission time Handle Problem Language Result Execution time Memory
387888 2021-04-09T11:13:59 Z AmShZ Swapping Cities (APIO20_swap) C++11
13 / 100
 1014 ms 109776 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], a[u.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 31 ms 47564 KB Output is correct
2 Correct 29 ms 47520 KB Output is correct
3 Correct 30 ms 47556 KB Output is correct
4 Correct 35 ms 47692 KB Output is correct
5 Correct 32 ms 48068 KB Output is correct
6 Correct 33 ms 48032 KB Output is correct
7 Correct 31 ms 48076 KB Output is correct
8 Correct 32 ms 48156 KB Output is correct
9 Correct 375 ms 90852 KB Output is correct
10 Correct 499 ms 102992 KB Output is correct
11 Correct 475 ms 101232 KB Output is correct
12 Correct 506 ms 104876 KB Output is correct
13 Correct 453 ms 108016 KB Output is correct
14 Correct 412 ms 89656 KB Output is correct
15 Correct 1014 ms 104512 KB Output is correct
16 Correct 993 ms 100292 KB Output is correct
17 Correct 975 ms 109776 KB Output is correct
18 Correct 938 ms 107208 KB Output is correct
19 Correct 216 ms 60580 KB Output is correct
20 Correct 950 ms 104688 KB Output is correct
21 Correct 967 ms 101368 KB Output is correct
22 Correct 1008 ms 106996 KB Output is correct
23 Correct 960 ms 107828 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47564 KB Output is correct
2 Correct 29 ms 47520 KB Output is correct
3 Correct 502 ms 96108 KB Output is correct
4 Correct 524 ms 98460 KB Output is correct
5 Correct 518 ms 97008 KB Output is correct
6 Correct 546 ms 98240 KB Output is correct
7 Correct 540 ms 97700 KB Output is correct
8 Correct 502 ms 95804 KB Output is correct
9 Correct 546 ms 97480 KB Output is correct
10 Correct 514 ms 95336 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47564 KB Output is correct
2 Correct 29 ms 47520 KB Output is correct
3 Correct 30 ms 47556 KB Output is correct
4 Correct 35 ms 47692 KB Output is correct
5 Correct 32 ms 48068 KB Output is correct
6 Correct 33 ms 48032 KB Output is correct
7 Correct 31 ms 48076 KB Output is correct
8 Correct 32 ms 48156 KB Output is correct
9 Correct 34 ms 47436 KB Output is correct
10 Correct 32 ms 47940 KB Output is correct
11 Correct 31 ms 48052 KB Output is correct
12 Correct 32 ms 47960 KB Output is correct
13 Correct 31 ms 47888 KB Output is correct
14 Correct 31 ms 47844 KB Output is correct
15 Incorrect 32 ms 48052 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47436 KB Output is correct
2 Correct 31 ms 47564 KB Output is correct
3 Correct 29 ms 47520 KB Output is correct
4 Correct 30 ms 47556 KB Output is correct
5 Correct 35 ms 47692 KB Output is correct
6 Correct 32 ms 48068 KB Output is correct
7 Correct 33 ms 48032 KB Output is correct
8 Correct 31 ms 48076 KB Output is correct
9 Correct 32 ms 48156 KB Output is correct
10 Correct 375 ms 90852 KB Output is correct
11 Correct 499 ms 102992 KB Output is correct
12 Correct 475 ms 101232 KB Output is correct
13 Correct 506 ms 104876 KB Output is correct
14 Correct 453 ms 108016 KB Output is correct
15 Correct 32 ms 47940 KB Output is correct
16 Correct 31 ms 48052 KB Output is correct
17 Correct 32 ms 47960 KB Output is correct
18 Correct 31 ms 47888 KB Output is correct
19 Correct 31 ms 47844 KB Output is correct
20 Incorrect 32 ms 48052 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47564 KB Output is correct
2 Correct 29 ms 47520 KB Output is correct
3 Correct 30 ms 47556 KB Output is correct
4 Correct 35 ms 47692 KB Output is correct
5 Correct 32 ms 48068 KB Output is correct
6 Correct 33 ms 48032 KB Output is correct
7 Correct 31 ms 48076 KB Output is correct
8 Correct 32 ms 48156 KB Output is correct
9 Correct 375 ms 90852 KB Output is correct
10 Correct 499 ms 102992 KB Output is correct
11 Correct 475 ms 101232 KB Output is correct
12 Correct 506 ms 104876 KB Output is correct
13 Correct 453 ms 108016 KB Output is correct
14 Correct 412 ms 89656 KB Output is correct
15 Correct 1014 ms 104512 KB Output is correct
16 Correct 993 ms 100292 KB Output is correct
17 Correct 975 ms 109776 KB Output is correct
18 Correct 938 ms 107208 KB Output is correct
19 Correct 502 ms 96108 KB Output is correct
20 Correct 524 ms 98460 KB Output is correct
21 Correct 518 ms 97008 KB Output is correct
22 Correct 546 ms 98240 KB Output is correct
23 Correct 540 ms 97700 KB Output is correct
24 Correct 502 ms 95804 KB Output is correct
25 Correct 546 ms 97480 KB Output is correct
26 Correct 514 ms 95336 KB Output is correct
27 Correct 32 ms 47940 KB Output is correct
28 Correct 31 ms 48052 KB Output is correct
29 Correct 32 ms 47960 KB Output is correct
30 Correct 31 ms 47888 KB Output is correct
31 Correct 31 ms 47844 KB Output is correct
32 Incorrect 32 ms 48052 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47436 KB Output is correct
2 Correct 31 ms 47564 KB Output is correct
3 Correct 29 ms 47520 KB Output is correct
4 Correct 30 ms 47556 KB Output is correct
5 Correct 35 ms 47692 KB Output is correct
6 Correct 32 ms 48068 KB Output is correct
7 Correct 33 ms 48032 KB Output is correct
8 Correct 31 ms 48076 KB Output is correct
9 Correct 32 ms 48156 KB Output is correct
10 Correct 375 ms 90852 KB Output is correct
11 Correct 499 ms 102992 KB Output is correct
12 Correct 475 ms 101232 KB Output is correct
13 Correct 506 ms 104876 KB Output is correct
14 Correct 453 ms 108016 KB Output is correct
15 Correct 412 ms 89656 KB Output is correct
16 Correct 1014 ms 104512 KB Output is correct
17 Correct 993 ms 100292 KB Output is correct
18 Correct 975 ms 109776 KB Output is correct
19 Correct 938 ms 107208 KB Output is correct
20 Correct 502 ms 96108 KB Output is correct
21 Correct 524 ms 98460 KB Output is correct
22 Correct 518 ms 97008 KB Output is correct
23 Correct 546 ms 98240 KB Output is correct
24 Correct 540 ms 97700 KB Output is correct
25 Correct 502 ms 95804 KB Output is correct
26 Correct 546 ms 97480 KB Output is correct
27 Correct 514 ms 95336 KB Output is correct
28 Correct 32 ms 47940 KB Output is correct
29 Correct 31 ms 48052 KB Output is correct
30 Correct 32 ms 47960 KB Output is correct
31 Correct 31 ms 47888 KB Output is correct
32 Correct 31 ms 47844 KB Output is correct
33 Incorrect 32 ms 48052 KB Output isn't correct
34 Halted 0 ms 0 KB -