oj.uz

Submission #387852

# Submission time Handle Problem Language Result Execution time Memory
387852 2021-04-09T09:40:30 Z AmShZ Swapping Cities (APIO20_swap) C++11
6 / 100
 812 ms 77864 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];
vector <pip> E;
vector <pii> adj[xn], G[xn];

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 = max(mx[i - 1][v].B, mx[i - 1][par[i - 1][v]].B);
	}
	for (pii u : adj[v]){
		if (u.A == par[0][v])
			continue;
		par[0][u.A] = v;
		mx[0][u.A] = {E[u.B].A, mn[v]};
		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);
		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);
		res = min(res, mx[0][v].B);
		ans = max(ans, mx[0][u].A);
		res = min(res, mx[0][u].B);
	}
	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:119:29: warning: unused variable 'w' [-Wunused-variable]
  119 |   int v = e.B.A, u = e.B.B, w = e.A;
      |                             ^
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:145:6: warning: unused variable 'lca' [-Wunused-variable]
  145 |  int lca = LCA(v, u), res = inf, ans = 0;
      |      ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28748 KB Output is correct
2 Correct 17 ms 28768 KB Output is correct
3 Correct 17 ms 28700 KB Output is correct
4 Correct 17 ms 28880 KB Output is correct
5 Correct 18 ms 29004 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29148 KB Output is correct
8 Correct 18 ms 29172 KB Output is correct
9 Correct 218 ms 60088 KB Output is correct
10 Correct 279 ms 69040 KB Output is correct
11 Correct 266 ms 67600 KB Output is correct
12 Correct 299 ms 70360 KB Output is correct
13 Correct 261 ms 73236 KB Output is correct
14 Correct 244 ms 58960 KB Output is correct
15 Correct 674 ms 70648 KB Output is correct
16 Correct 644 ms 67176 KB Output is correct
17 Correct 683 ms 74880 KB Output is correct
18 Correct 680 ms 72736 KB Output is correct
19 Correct 151 ms 41220 KB Output is correct
20 Correct 724 ms 74976 KB Output is correct
21 Correct 739 ms 72484 KB Output is correct
22 Correct 812 ms 77060 KB Output is correct
23 Correct 759 ms 77864 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28748 KB Output is correct
2 Correct 17 ms 28768 KB Output is correct
3 Incorrect 372 ms 61564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28748 KB Output is correct
2 Correct 17 ms 28768 KB Output is correct
3 Correct 17 ms 28700 KB Output is correct
4 Correct 17 ms 28880 KB Output is correct
5 Correct 18 ms 29004 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29148 KB Output is correct
8 Correct 18 ms 29172 KB Output is correct
9 Correct 17 ms 28684 KB Output is correct
10 Incorrect 18 ms 29076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28684 KB Output is correct
2 Correct 17 ms 28748 KB Output is correct
3 Correct 17 ms 28768 KB Output is correct
4 Correct 17 ms 28700 KB Output is correct
5 Correct 17 ms 28880 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29004 KB Output is correct
8 Correct 18 ms 29148 KB Output is correct
9 Correct 18 ms 29172 KB Output is correct
10 Correct 218 ms 60088 KB Output is correct
11 Correct 279 ms 69040 KB Output is correct
12 Correct 266 ms 67600 KB Output is correct
13 Correct 299 ms 70360 KB Output is correct
14 Correct 261 ms 73236 KB Output is correct
15 Incorrect 18 ms 29076 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28748 KB Output is correct
2 Correct 17 ms 28768 KB Output is correct
3 Correct 17 ms 28700 KB Output is correct
4 Correct 17 ms 28880 KB Output is correct
5 Correct 18 ms 29004 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29148 KB Output is correct
8 Correct 18 ms 29172 KB Output is correct
9 Correct 218 ms 60088 KB Output is correct
10 Correct 279 ms 69040 KB Output is correct
11 Correct 266 ms 67600 KB Output is correct
12 Correct 299 ms 70360 KB Output is correct
13 Correct 261 ms 73236 KB Output is correct
14 Correct 244 ms 58960 KB Output is correct
15 Correct 674 ms 70648 KB Output is correct
16 Correct 644 ms 67176 KB Output is correct
17 Correct 683 ms 74880 KB Output is correct
18 Correct 680 ms 72736 KB Output is correct
19 Incorrect 372 ms 61564 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28684 KB Output is correct
2 Correct 17 ms 28748 KB Output is correct
3 Correct 17 ms 28768 KB Output is correct
4 Correct 17 ms 28700 KB Output is correct
5 Correct 17 ms 28880 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29004 KB Output is correct
8 Correct 18 ms 29148 KB Output is correct
9 Correct 18 ms 29172 KB Output is correct
10 Correct 218 ms 60088 KB Output is correct
11 Correct 279 ms 69040 KB Output is correct
12 Correct 266 ms 67600 KB Output is correct
13 Correct 299 ms 70360 KB Output is correct
14 Correct 261 ms 73236 KB Output is correct
15 Correct 244 ms 58960 KB Output is correct
16 Correct 674 ms 70648 KB Output is correct
17 Correct 644 ms 67176 KB Output is correct
18 Correct 683 ms 74880 KB Output is correct
19 Correct 680 ms 72736 KB Output is correct
20 Incorrect 372 ms 61564 KB Output isn't correct
21 Halted 0 ms 0 KB -