oj.uz

Submission #387860

# Submission time Handle Problem Language Result Execution time Memory
387860 2021-04-09T10:13:00 Z AmShZ Swapping Cities (APIO20_swap) C++11
0 / 100
 802 ms 88852 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];
pii mx[xm][xn];
bool inmst[xn];
set <pii> st[xn], ts[xn], S[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);
	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;
		preDFS(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);
	a[v] = inf;
	if (SZ(st[rt]))
		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;
		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;
		ans = max(ans, mx[i][u].A);
		if (v != lca || i)
			res = min(res, mx[i][u].B);
		u = par[i][u];
	}
	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;
			}
		}
	}
	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
*/

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:130:29: warning: unused variable 'w' [-Wunused-variable]
  130 |   int v = e.B.A, u = e.B.B, w = e.A;
      |                             ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38092 KB Output is correct
2 Correct 23 ms 38064 KB Output is correct
3 Correct 22 ms 38092 KB Output is correct
4 Correct 24 ms 38356 KB Output is correct
5 Correct 24 ms 38468 KB Output is correct
6 Correct 24 ms 38572 KB Output is correct
7 Correct 23 ms 38476 KB Output is correct
8 Correct 26 ms 38604 KB Output is correct
9 Correct 257 ms 73784 KB Output is correct
10 Correct 326 ms 84192 KB Output is correct
11 Correct 308 ms 82504 KB Output is correct
12 Correct 338 ms 85680 KB Output is correct
13 Correct 302 ms 88852 KB Output is correct
14 Correct 294 ms 72636 KB Output is correct
15 Incorrect 802 ms 85756 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38092 KB Output is correct
2 Correct 23 ms 38064 KB Output is correct
3 Incorrect 409 ms 77416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38092 KB Output is correct
2 Correct 23 ms 38064 KB Output is correct
3 Correct 22 ms 38092 KB Output is correct
4 Correct 24 ms 38356 KB Output is correct
5 Correct 24 ms 38468 KB Output is correct
6 Correct 24 ms 38572 KB Output is correct
7 Correct 23 ms 38476 KB Output is correct
8 Correct 26 ms 38604 KB Output is correct
9 Correct 23 ms 38068 KB Output is correct
10 Correct 25 ms 38516 KB Output is correct
11 Correct 24 ms 38544 KB Output is correct
12 Correct 24 ms 38476 KB Output is correct
13 Correct 24 ms 38384 KB Output is correct
14 Correct 24 ms 38488 KB Output is correct
15 Incorrect 24 ms 38476 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 38068 KB Output is correct
2 Correct 22 ms 38092 KB Output is correct
3 Correct 23 ms 38064 KB Output is correct
4 Correct 22 ms 38092 KB Output is correct
5 Correct 24 ms 38356 KB Output is correct
6 Correct 24 ms 38468 KB Output is correct
7 Correct 24 ms 38572 KB Output is correct
8 Correct 23 ms 38476 KB Output is correct
9 Correct 26 ms 38604 KB Output is correct
10 Correct 257 ms 73784 KB Output is correct
11 Correct 326 ms 84192 KB Output is correct
12 Correct 308 ms 82504 KB Output is correct
13 Correct 338 ms 85680 KB Output is correct
14 Correct 302 ms 88852 KB Output is correct
15 Correct 25 ms 38516 KB Output is correct
16 Correct 24 ms 38544 KB Output is correct
17 Correct 24 ms 38476 KB Output is correct
18 Correct 24 ms 38384 KB Output is correct
19 Correct 24 ms 38488 KB Output is correct
20 Incorrect 24 ms 38476 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38092 KB Output is correct
2 Correct 23 ms 38064 KB Output is correct
3 Correct 22 ms 38092 KB Output is correct
4 Correct 24 ms 38356 KB Output is correct
5 Correct 24 ms 38468 KB Output is correct
6 Correct 24 ms 38572 KB Output is correct
7 Correct 23 ms 38476 KB Output is correct
8 Correct 26 ms 38604 KB Output is correct
9 Correct 257 ms 73784 KB Output is correct
10 Correct 326 ms 84192 KB Output is correct
11 Correct 308 ms 82504 KB Output is correct
12 Correct 338 ms 85680 KB Output is correct
13 Correct 302 ms 88852 KB Output is correct
14 Correct 294 ms 72636 KB Output is correct
15 Incorrect 802 ms 85756 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 38068 KB Output is correct
2 Correct 22 ms 38092 KB Output is correct
3 Correct 23 ms 38064 KB Output is correct
4 Correct 22 ms 38092 KB Output is correct
5 Correct 24 ms 38356 KB Output is correct
6 Correct 24 ms 38468 KB Output is correct
7 Correct 24 ms 38572 KB Output is correct
8 Correct 23 ms 38476 KB Output is correct
9 Correct 26 ms 38604 KB Output is correct
10 Correct 257 ms 73784 KB Output is correct
11 Correct 326 ms 84192 KB Output is correct
12 Correct 308 ms 82504 KB Output is correct
13 Correct 338 ms 85680 KB Output is correct
14 Correct 302 ms 88852 KB Output is correct
15 Correct 294 ms 72636 KB Output is correct
16 Incorrect 802 ms 85756 KB Output isn't correct
17 Halted 0 ms 0 KB -