oj.uz

Submission #387854

# Submission time Handle Problem Language Result Execution time Memory
387854 2021-04-09T09:43:25 Z AmShZ Swapping Cities (APIO20_swap) C++11
6 / 100
 717 ms 74912 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 = min(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 28748 KB Output is correct
3 Correct 18 ms 28728 KB Output is correct
4 Correct 18 ms 28932 KB Output is correct
5 Correct 18 ms 29028 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29132 KB Output is correct
8 Correct 19 ms 29124 KB Output is correct
9 Correct 219 ms 60044 KB Output is correct
10 Correct 283 ms 69272 KB Output is correct
11 Correct 275 ms 67532 KB Output is correct
12 Correct 301 ms 70344 KB Output is correct
13 Correct 276 ms 73192 KB Output is correct
14 Correct 264 ms 58972 KB Output is correct
15 Correct 674 ms 70740 KB Output is correct
16 Correct 689 ms 67180 KB Output is correct
17 Correct 631 ms 74912 KB Output is correct
18 Correct 623 ms 72748 KB Output is correct
19 Correct 159 ms 39156 KB Output is correct
20 Correct 676 ms 70832 KB Output is correct
21 Correct 643 ms 68176 KB Output is correct
22 Correct 717 ms 72640 KB Output is correct
23 Correct 625 ms 73376 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 28748 KB Output is correct
3 Incorrect 380 ms 61504 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 28748 KB Output is correct
3 Correct 18 ms 28728 KB Output is correct
4 Correct 18 ms 28932 KB Output is correct
5 Correct 18 ms 29028 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29132 KB Output is correct
8 Correct 19 ms 29124 KB Output is correct
9 Correct 16 ms 28748 KB Output is correct
10 Incorrect 18 ms 29020 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28748 KB Output is correct
2 Correct 17 ms 28748 KB Output is correct
3 Correct 17 ms 28748 KB Output is correct
4 Correct 18 ms 28728 KB Output is correct
5 Correct 18 ms 28932 KB Output is correct
6 Correct 18 ms 29028 KB Output is correct
7 Correct 18 ms 29004 KB Output is correct
8 Correct 18 ms 29132 KB Output is correct
9 Correct 19 ms 29124 KB Output is correct
10 Correct 219 ms 60044 KB Output is correct
11 Correct 283 ms 69272 KB Output is correct
12 Correct 275 ms 67532 KB Output is correct
13 Correct 301 ms 70344 KB Output is correct
14 Correct 276 ms 73192 KB Output is correct
15 Incorrect 18 ms 29020 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 28748 KB Output is correct
3 Correct 18 ms 28728 KB Output is correct
4 Correct 18 ms 28932 KB Output is correct
5 Correct 18 ms 29028 KB Output is correct
6 Correct 18 ms 29004 KB Output is correct
7 Correct 18 ms 29132 KB Output is correct
8 Correct 19 ms 29124 KB Output is correct
9 Correct 219 ms 60044 KB Output is correct
10 Correct 283 ms 69272 KB Output is correct
11 Correct 275 ms 67532 KB Output is correct
12 Correct 301 ms 70344 KB Output is correct
13 Correct 276 ms 73192 KB Output is correct
14 Correct 264 ms 58972 KB Output is correct
15 Correct 674 ms 70740 KB Output is correct
16 Correct 689 ms 67180 KB Output is correct
17 Correct 631 ms 74912 KB Output is correct
18 Correct 623 ms 72748 KB Output is correct
19 Incorrect 380 ms 61504 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28748 KB Output is correct
2 Correct 17 ms 28748 KB Output is correct
3 Correct 17 ms 28748 KB Output is correct
4 Correct 18 ms 28728 KB Output is correct
5 Correct 18 ms 28932 KB Output is correct
6 Correct 18 ms 29028 KB Output is correct
7 Correct 18 ms 29004 KB Output is correct
8 Correct 18 ms 29132 KB Output is correct
9 Correct 19 ms 29124 KB Output is correct
10 Correct 219 ms 60044 KB Output is correct
11 Correct 283 ms 69272 KB Output is correct
12 Correct 275 ms 67532 KB Output is correct
13 Correct 301 ms 70344 KB Output is correct
14 Correct 276 ms 73192 KB Output is correct
15 Correct 264 ms 58972 KB Output is correct
16 Correct 674 ms 70740 KB Output is correct
17 Correct 689 ms 67180 KB Output is correct
18 Correct 631 ms 74912 KB Output is correct
19 Correct 623 ms 72748 KB Output is correct
20 Incorrect 380 ms 61504 KB Output isn't correct
21 Halted 0 ms 0 KB -