oj.uz

Submission #319952

# Submission time Handle Problem Language Result Execution time Memory
319952 2020-11-06T22:41:15 Z Blagojce Swapping Cities (APIO20_swap) C++11
36 / 100
 667 ms 45532 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 1e5+5;
mt19937 _rand(time(NULL));

#include "swap.h"

vector<pii> g[mxn];
int n, m;
int sparse[mxn][20];
int mxw[mxn][20];

int depth[mxn];

int _c[mxn];
int dp[mxn];
void dfs(int u, int p, int val, int val2){
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	
	mxw[u][0] = val2;
	fr(i, 1, 20) mxw[u][i] = max(mxw[u][i-1], mxw[sparse[u][i-1]][i-1]);
	
	int mi1 = i_inf, c1 = -1;
	int mi2 = i_inf;
	
	for(auto e : g[u]){
		if(e.st == p) continue;
		if(e.nd < mi1){
			mi2 = mi1;
			mi1 = e.nd;
			c1 = e.st;
		}
		else if(e.nd < mi2){
			mi2 = e.nd;
		}
	}
	dp[u] = _c[u];
	for(auto e : g[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u] + 1;
		if(e.st != c1){
			dfs(e.st, u, mi1, e.nd);
		}
		else{
			dfs(e.st, u, mi2, e.nd);
		}
		dp[u] = min(dp[u], max(dp[e.st], e.nd));
	}
}
int dpup[mxn];
void dfs2(int u, int p, int carry){
	carry = min(carry, _c[u]);
	dpup[u] = carry;
	int id = p;
	int min1 = carry;
	int min2 = i_inf;
	for(auto e : g[u]){
		if(e.st == p) continue;
		int cand1 = max(dp[e.st], e.nd);
		if(cand1 < min1){
			min2 = min1;
			id = e.st;
			min1 = cand1;
		}else if(cand1 < min2){
			min2 = cand1;
		}
	}
	for(auto e : g[u]){
		if(e.st == p) continue;
		if(e.st == id){
			dfs2(e.st, u, max(e.nd, min2));
		}
		else{
			dfs2(e.st, u, max(e.nd, min1));
		}
	}
	

}

int lca(int a, int b){
	int mind = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a] - (1<<i) >= mind) a = sparse[a][i];
		if(depth[b] - (1<<i) >= mind) b = sparse[b][i];
	}
	if(a == b) return a;
	
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
int cost(int u, int p){
	int ret = 0;
	for(int i = 19; i >= 0; i --){
		if(depth[u] - (1<<i) >= depth[p]){
			ret = max(ret, mxw[u][i]);
			u = sparse[u][i];
		}
	}
	return ret;
}

int link[mxn];
int sz[mxn];
bool used[200005];
int findx(int x){
	if(x == link[x]) return x;
	link[x] = findx(link[x]);
	return link[x];
}
int secondbest = i_inf;
void unite(int a, int b, int wi, int i){
	int u = a, v = b;
	
	a = findx(a);
	b = findx(b);
	if(a == b){
		secondbest = min(secondbest, wi);
		return;
	}
	used[i] = true;
	if(sz[a] < sz[b]) swap(a, b);
	link[b] = a;
	sz[a] += sz[b];
	g[u].pb({v, wi});
	g[v].pb({u, wi});
	
}
vector<pii> G[mxn];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
	n = N, m = M;
	vector<pii> S;
	fr(i, 0, m){
		S.pb({W[i], i});
	}
	sort(all(S));
	fr(i, 0, n){
		link[i] = i;
		sz[i] = 1;
	}
	for(auto edge : S){
		int u = U[edge.nd];
		int v = V[edge.nd];
		unite(u, v, edge.st, edge.nd);
	}
	fr(i, 0, m){
		G[U[i]].pb({W[i], i});
		G[V[i]].pb({W[i], i});
	}
	
	fr(i, 0, n){
		sort(all(g[i]), [](const pii A, const pii B){
			return A.nd < B.nd;
		});
		
		sort(all(G[i]));
	}
	fr(i, 0, n){
		_c[i] = i_inf;
		if((int)g[i].size() >= 3) _c[i] = g[i][2].nd;
		for(auto u : G[i]){
			if(used[u.nd]) continue;
			_c[i] = min(_c[i], u.st);
			break;
		}
		
	}
	
	dfs(0, 0, i_inf, i_inf);
	dfs2(0, 0, i_inf);
	
	
}

	
int line = 0;
int getMinimumFuelCapacity(int X, int Y){
	int k = lca(X, Y);
	
	if(X == k){
		int c = min(secondbest, max(min(dp[k], dpup[k]), cost(Y, k)));
		if(c == i_inf) c = -1;
		return c;
	}
	else if(Y == k){
		int c = min(secondbest, max(min(dp[k], dpup[k]), cost(X, k)));
		if(c == i_inf) c = -1;
		return c;
		
	}
	else{
		int c = min(secondbest, max(min(dp[k], dpup[k]), max(cost(X, k), cost(Y, k))));
		if(c == i_inf) c = -1;
		return c;
	}
}/*
int main(){
	freopen("inp.txt", "r",stdin);
	//freopen("out.txt", "w", stdout);
	cin >> n >> m;
	vector<int> U(m);
	vector<int> V(m);
	vector<int> W(m);

	fr(i, 0, m){
		cin >> U[i] >> V[i] >> W[i];
	}
	
	init(n, m, U, V, W);
	int cc;
	cin >> cc;
	while(cc--){
		int i, j;
		cin >> i >> j;
		++line;
		int ans = getMinimumFuelCapacity(i, j);
		if(line == 1200) cout<<ans<<endl;
	}
	
	


}*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5112 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 6 ms 5484 KB Output is correct
8 Correct 6 ms 5484 KB Output is correct
9 Correct 193 ms 32852 KB Output is correct
10 Correct 262 ms 40656 KB Output is correct
11 Correct 286 ms 39512 KB Output is correct
12 Correct 260 ms 41816 KB Output is correct
13 Correct 239 ms 43868 KB Output is correct
14 Correct 230 ms 32344 KB Output is correct
15 Correct 634 ms 42380 KB Output is correct
16 Correct 624 ms 39384 KB Output is correct
17 Correct 569 ms 45532 KB Output is correct
18 Correct 566 ms 43864 KB Output is correct
19 Correct 164 ms 16268 KB Output is correct
20 Correct 635 ms 42260 KB Output is correct
21 Correct 606 ms 40244 KB Output is correct
22 Correct 632 ms 43820 KB Output is correct
23 Correct 558 ms 44332 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5112 KB Output is correct
3 Correct 303 ms 37144 KB Output is correct
4 Correct 305 ms 38320 KB Output is correct
5 Correct 315 ms 37888 KB Output is correct
6 Correct 297 ms 38196 KB Output is correct
7 Correct 306 ms 38104 KB Output is correct
8 Correct 294 ms 36908 KB Output is correct
9 Correct 294 ms 37848 KB Output is correct
10 Correct 296 ms 36672 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5112 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 6 ms 5484 KB Output is correct
8 Correct 6 ms 5484 KB Output is correct
9 Correct 193 ms 32852 KB Output is correct
10 Correct 262 ms 40656 KB Output is correct
11 Correct 286 ms 39512 KB Output is correct
12 Correct 260 ms 41816 KB Output is correct
13 Correct 239 ms 43868 KB Output is correct
14 Correct 230 ms 32344 KB Output is correct
15 Correct 634 ms 42380 KB Output is correct
16 Correct 624 ms 39384 KB Output is correct
17 Correct 569 ms 45532 KB Output is correct
18 Correct 566 ms 43864 KB Output is correct
19 Correct 303 ms 37144 KB Output is correct
20 Correct 305 ms 38320 KB Output is correct
21 Correct 315 ms 37888 KB Output is correct
22 Correct 297 ms 38196 KB Output is correct
23 Correct 306 ms 38104 KB Output is correct
24 Correct 294 ms 36908 KB Output is correct
25 Correct 294 ms 37848 KB Output is correct
26 Correct 296 ms 36672 KB Output is correct
27 Correct 5 ms 5356 KB Output is correct
28 Correct 5 ms 5356 KB Output is correct
29 Correct 6 ms 5356 KB Output is correct
30 Correct 5 ms 5356 KB Output is correct
31 Correct 6 ms 5356 KB Output is correct
32 Correct 5 ms 5376 KB Output is correct
33 Correct 5 ms 5356 KB Output is correct
34 Correct 5 ms 5484 KB Output is correct
35 Correct 5 ms 5356 KB Output is correct
36 Correct 23 ms 9188 KB Output is correct
37 Correct 279 ms 40920 KB Output is correct
38 Correct 326 ms 37464 KB Output is correct
39 Correct 253 ms 35416 KB Output is correct
40 Correct 244 ms 34592 KB Output is correct
41 Correct 224 ms 33892 KB Output is correct
42 Correct 192 ms 31960 KB Output is correct
43 Correct 265 ms 38876 KB Output is correct
44 Correct 283 ms 39896 KB Output is correct
45 Correct 255 ms 41624 KB Output is correct
46 Correct 218 ms 35672 KB Output is correct
47 Correct 41 ms 9344 KB Output is correct
48 Correct 667 ms 40748 KB Output is correct
49 Correct 634 ms 38828 KB Output is correct
50 Correct 621 ms 37680 KB Output is correct
51 Correct 550 ms 36924 KB Output is correct
52 Correct 485 ms 35096 KB Output is correct
53 Correct 376 ms 29116 KB Output is correct
54 Correct 664 ms 40376 KB Output is correct
55 Correct 642 ms 41456 KB Output is correct
56 Correct 569 ms 44588 KB Output is correct
57 Correct 461 ms 38216 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct