답안 #319955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319955	2020-11-06T22:50:53 Z	Blagojce	자매 도시 (APIO20_swap)	C++11	100 / 100	701 ms	43968 KB

swap

#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){
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	
	mxw[u][0] = val;
	fr(i, 1, 20) mxw[u][i] = max(mxw[u][i-1], mxw[sparse[u][i-1]][i-1]);
	
	dp[u] = _c[u];
	for(auto e : g[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u] + 1;
		dfs(e.st, u, 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];
}
void unite(int a, int b, int wi, int i){
	int u = a, v = b;
	a = findx(a);
	b = findx(b);
	if(a == b) 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);
	dfs2(0, 0, i_inf);
}

int line = 0;
int getMinimumFuelCapacity(int X, int Y){
	int k = lca(X, Y);	
	int c = max(min(dp[k], dpup[k]), max(cost(X, k), cost(Y, k)));
	if(c == i_inf) c = -1;
	return c;
}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5260 KB	Output is correct
5	Correct	6 ms	5484 KB	Output is correct
6	Correct	5 ms	5356 KB	Output is correct
7	Correct	5 ms	5356 KB	Output is correct
8	Correct	5 ms	5356 KB	Output is correct
9	Correct	190 ms	30548 KB	Output is correct
10	Correct	245 ms	37336 KB	Output is correct
11	Correct	248 ms	36440 KB	Output is correct
12	Correct	289 ms	38520 KB	Output is correct
13	Correct	240 ms	40280 KB	Output is correct
14	Correct	218 ms	29912 KB	Output is correct
15	Correct	586 ms	38872 KB	Output is correct
16	Correct	603 ms	36440 KB	Output is correct
17	Correct	614 ms	41816 KB	Output is correct
18	Correct	569 ms	40408 KB	Output is correct
19	Correct	137 ms	13928 KB	Output is correct
20	Correct	566 ms	38992 KB	Output is correct
21	Correct	598 ms	37176 KB	Output is correct
22	Correct	611 ms	40356 KB	Output is correct
23	Correct	562 ms	40872 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	281 ms	34840 KB	Output is correct
4	Correct	288 ms	36140 KB	Output is correct
5	Correct	314 ms	35456 KB	Output is correct
6	Correct	299 ms	36164 KB	Output is correct
7	Correct	292 ms	35804 KB	Output is correct
8	Correct	290 ms	34732 KB	Output is correct
9	Correct	292 ms	35676 KB	Output is correct
10	Correct	289 ms	34496 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5248 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5100 KB	Output is correct
5	Correct	4 ms	5260 KB	Output is correct
6	Correct	6 ms	5484 KB	Output is correct
7	Correct	5 ms	5356 KB	Output is correct
8	Correct	5 ms	5356 KB	Output is correct
9	Correct	5 ms	5356 KB	Output is correct
10	Correct	5 ms	5356 KB	Output is correct
11	Correct	5 ms	5356 KB	Output is correct
12	Correct	5 ms	5356 KB	Output is correct
13	Correct	4 ms	5356 KB	Output is correct
14	Correct	4 ms	5356 KB	Output is correct
15	Correct	5 ms	5356 KB	Output is correct
16	Correct	5 ms	5608 KB	Output is correct
17	Correct	5 ms	5356 KB	Output is correct
18	Correct	5 ms	5484 KB	Output is correct
19	Correct	4 ms	5228 KB	Output is correct
20	Correct	5 ms	5356 KB	Output is correct
21	Correct	5 ms	5356 KB	Output is correct
22	Correct	5 ms	5260 KB	Output is correct
23	Correct	5 ms	5356 KB	Output is correct
24	Correct	5 ms	5516 KB	Output is correct
25	Correct	5 ms	5484 KB	Output is correct
26	Correct	7 ms	5484 KB	Output is correct
27	Correct	5 ms	5356 KB	Output is correct
28	Correct	5 ms	5484 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5248 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5100 KB	Output is correct
5	Correct	4 ms	5260 KB	Output is correct
6	Correct	6 ms	5484 KB	Output is correct
7	Correct	5 ms	5356 KB	Output is correct
8	Correct	5 ms	5356 KB	Output is correct
9	Correct	5 ms	5356 KB	Output is correct
10	Correct	190 ms	30548 KB	Output is correct
11	Correct	245 ms	37336 KB	Output is correct
12	Correct	248 ms	36440 KB	Output is correct
13	Correct	289 ms	38520 KB	Output is correct
14	Correct	240 ms	40280 KB	Output is correct
15	Correct	5 ms	5356 KB	Output is correct
16	Correct	5 ms	5356 KB	Output is correct
17	Correct	5 ms	5356 KB	Output is correct
18	Correct	4 ms	5356 KB	Output is correct
19	Correct	4 ms	5356 KB	Output is correct
20	Correct	5 ms	5356 KB	Output is correct
21	Correct	5 ms	5608 KB	Output is correct
22	Correct	5 ms	5356 KB	Output is correct
23	Correct	5 ms	5484 KB	Output is correct
24	Correct	20 ms	8940 KB	Output is correct
25	Correct	256 ms	37972 KB	Output is correct
26	Correct	249 ms	35468 KB	Output is correct
27	Correct	227 ms	33520 KB	Output is correct
28	Correct	224 ms	32696 KB	Output is correct
29	Correct	207 ms	32472 KB	Output is correct
30	Correct	178 ms	30296 KB	Output is correct
31	Correct	253 ms	36184 KB	Output is correct
32	Correct	255 ms	37212 KB	Output is correct
33	Correct	223 ms	38556 KB	Output is correct
34	Correct	210 ms	33752 KB	Output is correct
35	Correct	4 ms	5228 KB	Output is correct
36	Correct	5 ms	5356 KB	Output is correct
37	Correct	5 ms	5356 KB	Output is correct
38	Correct	5 ms	5260 KB	Output is correct
39	Correct	5 ms	5356 KB	Output is correct
40	Correct	5 ms	5516 KB	Output is correct
41	Correct	5 ms	5484 KB	Output is correct
42	Correct	7 ms	5484 KB	Output is correct
43	Correct	5 ms	5356 KB	Output is correct
44	Correct	5 ms	5484 KB	Output is correct
45	Correct	201 ms	31568 KB	Output is correct
46	Correct	236 ms	34392 KB	Output is correct
47	Correct	205 ms	32632 KB	Output is correct
48	Correct	206 ms	32984 KB	Output is correct
49	Correct	104 ms	15316 KB	Output is correct
50	Correct	81 ms	13916 KB	Output is correct
51	Correct	165 ms	27096 KB	Output is correct
52	Correct	291 ms	38548 KB	Output is correct
53	Correct	291 ms	38228 KB	Output is correct
54	Correct	337 ms	42452 KB	Output is correct
55	Correct	232 ms	40020 KB	Output is correct
56	Correct	270 ms	37716 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5260 KB	Output is correct
5	Correct	6 ms	5484 KB	Output is correct
6	Correct	5 ms	5356 KB	Output is correct
7	Correct	5 ms	5356 KB	Output is correct
8	Correct	5 ms	5356 KB	Output is correct
9	Correct	190 ms	30548 KB	Output is correct
10	Correct	245 ms	37336 KB	Output is correct
11	Correct	248 ms	36440 KB	Output is correct
12	Correct	289 ms	38520 KB	Output is correct
13	Correct	240 ms	40280 KB	Output is correct
14	Correct	218 ms	29912 KB	Output is correct
15	Correct	586 ms	38872 KB	Output is correct
16	Correct	603 ms	36440 KB	Output is correct
17	Correct	614 ms	41816 KB	Output is correct
18	Correct	569 ms	40408 KB	Output is correct
19	Correct	281 ms	34840 KB	Output is correct
20	Correct	288 ms	36140 KB	Output is correct
21	Correct	314 ms	35456 KB	Output is correct
22	Correct	299 ms	36164 KB	Output is correct
23	Correct	292 ms	35804 KB	Output is correct
24	Correct	290 ms	34732 KB	Output is correct
25	Correct	292 ms	35676 KB	Output is correct
26	Correct	289 ms	34496 KB	Output is correct
27	Correct	5 ms	5356 KB	Output is correct
28	Correct	5 ms	5356 KB	Output is correct
29	Correct	5 ms	5356 KB	Output is correct
30	Correct	4 ms	5356 KB	Output is correct
31	Correct	4 ms	5356 KB	Output is correct
32	Correct	5 ms	5356 KB	Output is correct
33	Correct	5 ms	5608 KB	Output is correct
34	Correct	5 ms	5356 KB	Output is correct
35	Correct	5 ms	5484 KB	Output is correct
36	Correct	20 ms	8940 KB	Output is correct
37	Correct	256 ms	37972 KB	Output is correct
38	Correct	249 ms	35468 KB	Output is correct
39	Correct	227 ms	33520 KB	Output is correct
40	Correct	224 ms	32696 KB	Output is correct
41	Correct	207 ms	32472 KB	Output is correct
42	Correct	178 ms	30296 KB	Output is correct
43	Correct	253 ms	36184 KB	Output is correct
44	Correct	255 ms	37212 KB	Output is correct
45	Correct	223 ms	38556 KB	Output is correct
46	Correct	210 ms	33752 KB	Output is correct
47	Correct	33 ms	8832 KB	Output is correct
48	Correct	631 ms	37960 KB	Output is correct
49	Correct	593 ms	36392 KB	Output is correct
50	Correct	546 ms	35500 KB	Output is correct
51	Correct	515 ms	34748 KB	Output is correct
52	Correct	455 ms	33188 KB	Output is correct
53	Correct	325 ms	27072 KB	Output is correct
54	Correct	610 ms	37800 KB	Output is correct
55	Correct	610 ms	38568 KB	Output is correct
56	Correct	552 ms	41256 KB	Output is correct
57	Correct	438 ms	36140 KB	Output is correct

Subtask #6

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5248 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5100 KB	Output is correct
5	Correct	4 ms	5260 KB	Output is correct
6	Correct	6 ms	5484 KB	Output is correct
7	Correct	5 ms	5356 KB	Output is correct
8	Correct	5 ms	5356 KB	Output is correct
9	Correct	5 ms	5356 KB	Output is correct
10	Correct	190 ms	30548 KB	Output is correct
11	Correct	245 ms	37336 KB	Output is correct
12	Correct	248 ms	36440 KB	Output is correct
13	Correct	289 ms	38520 KB	Output is correct
14	Correct	240 ms	40280 KB	Output is correct
15	Correct	218 ms	29912 KB	Output is correct
16	Correct	586 ms	38872 KB	Output is correct
17	Correct	603 ms	36440 KB	Output is correct
18	Correct	614 ms	41816 KB	Output is correct
19	Correct	569 ms	40408 KB	Output is correct
20	Correct	281 ms	34840 KB	Output is correct
21	Correct	288 ms	36140 KB	Output is correct
22	Correct	314 ms	35456 KB	Output is correct
23	Correct	299 ms	36164 KB	Output is correct
24	Correct	292 ms	35804 KB	Output is correct
25	Correct	290 ms	34732 KB	Output is correct
26	Correct	292 ms	35676 KB	Output is correct
27	Correct	289 ms	34496 KB	Output is correct
28	Correct	5 ms	5356 KB	Output is correct
29	Correct	5 ms	5356 KB	Output is correct
30	Correct	5 ms	5356 KB	Output is correct
31	Correct	4 ms	5356 KB	Output is correct
32	Correct	4 ms	5356 KB	Output is correct
33	Correct	5 ms	5356 KB	Output is correct
34	Correct	5 ms	5608 KB	Output is correct
35	Correct	5 ms	5356 KB	Output is correct
36	Correct	5 ms	5484 KB	Output is correct
37	Correct	20 ms	8940 KB	Output is correct
38	Correct	256 ms	37972 KB	Output is correct
39	Correct	249 ms	35468 KB	Output is correct
40	Correct	227 ms	33520 KB	Output is correct
41	Correct	224 ms	32696 KB	Output is correct
42	Correct	207 ms	32472 KB	Output is correct
43	Correct	178 ms	30296 KB	Output is correct
44	Correct	253 ms	36184 KB	Output is correct
45	Correct	255 ms	37212 KB	Output is correct
46	Correct	223 ms	38556 KB	Output is correct
47	Correct	210 ms	33752 KB	Output is correct
48	Correct	33 ms	8832 KB	Output is correct
49	Correct	631 ms	37960 KB	Output is correct
50	Correct	593 ms	36392 KB	Output is correct
51	Correct	546 ms	35500 KB	Output is correct
52	Correct	515 ms	34748 KB	Output is correct
53	Correct	455 ms	33188 KB	Output is correct
54	Correct	325 ms	27072 KB	Output is correct
55	Correct	610 ms	37800 KB	Output is correct
56	Correct	610 ms	38568 KB	Output is correct
57	Correct	552 ms	41256 KB	Output is correct
58	Correct	438 ms	36140 KB	Output is correct
59	Correct	137 ms	13928 KB	Output is correct
60	Correct	566 ms	38992 KB	Output is correct
61	Correct	598 ms	37176 KB	Output is correct
62	Correct	611 ms	40356 KB	Output is correct
63	Correct	562 ms	40872 KB	Output is correct
64	Correct	4 ms	5228 KB	Output is correct
65	Correct	5 ms	5356 KB	Output is correct
66	Correct	5 ms	5356 KB	Output is correct
67	Correct	5 ms	5260 KB	Output is correct
68	Correct	5 ms	5356 KB	Output is correct
69	Correct	5 ms	5516 KB	Output is correct
70	Correct	5 ms	5484 KB	Output is correct
71	Correct	7 ms	5484 KB	Output is correct
72	Correct	5 ms	5356 KB	Output is correct
73	Correct	5 ms	5484 KB	Output is correct
74	Correct	201 ms	31568 KB	Output is correct
75	Correct	236 ms	34392 KB	Output is correct
76	Correct	205 ms	32632 KB	Output is correct
77	Correct	206 ms	32984 KB	Output is correct
78	Correct	104 ms	15316 KB	Output is correct
79	Correct	81 ms	13916 KB	Output is correct
80	Correct	165 ms	27096 KB	Output is correct
81	Correct	291 ms	38548 KB	Output is correct
82	Correct	291 ms	38228 KB	Output is correct
83	Correct	337 ms	42452 KB	Output is correct
84	Correct	232 ms	40020 KB	Output is correct
85	Correct	270 ms	37716 KB	Output is correct
86	Correct	109 ms	15520 KB	Output is correct
87	Correct	564 ms	36136 KB	Output is correct
88	Correct	569 ms	36392 KB	Output is correct
89	Correct	394 ms	32952 KB	Output is correct
90	Correct	220 ms	16472 KB	Output is correct
91	Correct	235 ms	17748 KB	Output is correct
92	Correct	358 ms	28788 KB	Output is correct
93	Correct	630 ms	40356 KB	Output is correct
94	Correct	500 ms	39892 KB	Output is correct
95	Correct	701 ms	43968 KB	Output is correct
96	Correct	578 ms	39228 KB	Output is correct
97	Correct	458 ms	37484 KB	Output is correct