답안 #966886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966886	2024-04-20T14:29:51 Z	penguin133	자매 도시 (APIO20_swap)	C++17	100 / 100	241 ms	46272 KB

swap

#include <bits/stdc++.h>
using namespace std;
#include "swap.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector <int> waiting[200005];
int par[200005], val[200005], deg[200005], good[200005], up[20][200005], dep[200005];
int cnt = 1;
pi adj[200005];
int getr(int x){return par[x] == x ? x : par[x] = getr(par[x]);}
void merge(int a, int b, int c){
	a = getr(a); b = getr(b);
	if(a == b)return;
	par[a] = par[b] = up[0][a] = up[0][b] = par[cnt];
	val[cnt] = c;
	adj[cnt] = {a, b};
	//good[cnt] = 1;
	cnt++;
}
 
int par2[200005];
int g2(int x){return par2[x] == x ? x : par2[x] = g2(par2[x]);}
void m2(int a, int b){par2[g2(b)] = g2(a);}
 
void dfs(int x, int d){
	//cout << x << '\n';
	dep[x] = d;
	if(adj[x].fi == adj[x].se)return;
	dfs(adj[x].fi, d + 1);
	dfs(adj[x].se, d + 1);
}
 
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] -dep[u];
	for(int i = 0; i <= 19; i++)if(df >> i & 1)v = up[i][v];
	if(u ==v )return u;
	for(int i = 19; i >=0 ; i--)if(up[i][u] != up[i][v])u = up[i][u], v = up[i][v];
	return up[0][u];
}
 
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	vector <pii> bb;
	cnt = N;
	for(int i = 0; i < 2 * N; i++)par[i] = par2[i] = i;
	for(int i = 0; i < M; i++)bb.push_back({W[i], {U[i], V[i]}});
	sort(bb.begin(), bb.end());
	for(auto i : bb){
		int a = i.se.fi, b = i.se.se, w = i.fi;
		if(g2(a) == g2(b)){
			good[getr(a)] = 1;
			good[getr(b)] = 1;
			queue <int> q;
			q.push(a);
			q.push(b);
			merge(a, b, w);
			while(!q.empty()){
				int x = q.front(); q.pop();
				vector <int> aa = waiting[x];
				waiting[x].clear();
				for(auto j : aa){
				    if(getr(j) != getr(x)){
						merge(x, j, w);
    			        q.push(j);
    			    }
				}
			}
		}
		else{
			m2(a, b);
			//if(getr(a) != a || getr(b) != b)merge(a, b, w);
			if(getr(a) != a || getr(b) != b){
				queue <int> q;
					q.push(a);
					q.push(b);
					merge(a, b, w);
					while(!q.empty()){
						int x = q.front(); q.pop();
						vector <int> aa = waiting[x];
						waiting[x].clear();
						for(auto j : aa){
						    if(getr(j) != getr(x)){
						        merge(x, j, w);
						        q.push(j);
						    }
						}
					}
			}
			else{
				deg[a]++; deg[b]++;
				if(max(deg[a], deg[b]) >= 3){
					good[getr(a)] = good[getr(b)] = 1;
					
					queue <int> q;
					q.push(a);
					q.push(b);
					merge(a, b, w);
					while(!q.empty()){
						int x = q.front(); q.pop();
						vector <int> aa = waiting[x];
						waiting[x].clear();
						for(auto j : aa){
						    if(getr(j) != getr(x)){
						        merge(x, j, w);
						        q.push(j);
						    }
						}
					}
				}
				else waiting[a].push_back(b), waiting[b].push_back(a);
			}
		}
	}
	for(int i = cnt - 1; i >= N; i--)if(!dep[i])dfs(i, 1);
	for(int i = 1; i <= 19; i++)for(int j = 0; j < 2 * N; j++)up[i][j] = up[i - 1][up[i - 1][j]];
}
 
int getMinimumFuelCapacity(int X, int Y) {
  if(getr(X) != getr(Y))return -1;
  //cout << lca(X, Y) << ' ';
  return val[lca(X, Y)];
}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	22620 KB	Output is correct
2	Correct	4 ms	22620 KB	Output is correct
3	Correct	4 ms	22872 KB	Output is correct
4	Correct	5 ms	22620 KB	Output is correct
5	Correct	4 ms	22880 KB	Output is correct
6	Correct	4 ms	22872 KB	Output is correct
7	Correct	4 ms	22876 KB	Output is correct
8	Correct	4 ms	22876 KB	Output is correct
9	Correct	48 ms	32200 KB	Output is correct
10	Correct	59 ms	33768 KB	Output is correct
11	Correct	50 ms	33476 KB	Output is correct
12	Correct	55 ms	33888 KB	Output is correct
13	Correct	50 ms	34400 KB	Output is correct
14	Correct	45 ms	32456 KB	Output is correct
15	Correct	89 ms	37576 KB	Output is correct
16	Correct	88 ms	37320 KB	Output is correct
17	Correct	91 ms	37980 KB	Output is correct
18	Correct	89 ms	38296 KB	Output is correct
19	Correct	69 ms	33368 KB	Output is correct
20	Correct	211 ms	40764 KB	Output is correct
21	Correct	181 ms	40828 KB	Output is correct
22	Correct	205 ms	41376 KB	Output is correct
23	Correct	190 ms	41360 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	22620 KB	Output is correct
2	Correct	4 ms	22620 KB	Output is correct
3	Correct	206 ms	37564 KB	Output is correct
4	Correct	171 ms	37380 KB	Output is correct
5	Correct	166 ms	37612 KB	Output is correct
6	Correct	178 ms	37208 KB	Output is correct
7	Correct	174 ms	37568 KB	Output is correct
8	Correct	240 ms	37408 KB	Output is correct
9	Correct	168 ms	37312 KB	Output is correct
10	Correct	160 ms	37348 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	22620 KB	Output is correct
2	Correct	4 ms	22620 KB	Output is correct
3	Correct	4 ms	22872 KB	Output is correct
4	Correct	5 ms	22620 KB	Output is correct
5	Correct	4 ms	22880 KB	Output is correct
6	Correct	4 ms	22872 KB	Output is correct
7	Correct	4 ms	22876 KB	Output is correct
8	Correct	4 ms	22876 KB	Output is correct
9	Correct	4 ms	26716 KB	Output is correct
10	Correct	5 ms	26972 KB	Output is correct
11	Correct	5 ms	27224 KB	Output is correct
12	Correct	5 ms	26972 KB	Output is correct
13	Correct	5 ms	26716 KB	Output is correct
14	Correct	5 ms	26868 KB	Output is correct
15	Correct	5 ms	26972 KB	Output is correct
16	Correct	5 ms	26972 KB	Output is correct
17	Correct	5 ms	26716 KB	Output is correct
18	Correct	5 ms	26972 KB	Output is correct
19	Correct	5 ms	26716 KB	Output is correct
20	Correct	5 ms	26972 KB	Output is correct
21	Correct	5 ms	26972 KB	Output is correct
22	Correct	5 ms	26972 KB	Output is correct
23	Correct	6 ms	26716 KB	Output is correct
24	Correct	5 ms	26972 KB	Output is correct
25	Correct	5 ms	26968 KB	Output is correct
26	Correct	5 ms	27016 KB	Output is correct
27	Correct	5 ms	26864 KB	Output is correct
28	Correct	5 ms	26972 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	26716 KB	Output is correct
2	Correct	5 ms	22620 KB	Output is correct
3	Correct	4 ms	22620 KB	Output is correct
4	Correct	4 ms	22872 KB	Output is correct
5	Correct	5 ms	22620 KB	Output is correct
6	Correct	4 ms	22880 KB	Output is correct
7	Correct	4 ms	22872 KB	Output is correct
8	Correct	4 ms	22876 KB	Output is correct
9	Correct	4 ms	22876 KB	Output is correct
10	Correct	48 ms	32200 KB	Output is correct
11	Correct	59 ms	33768 KB	Output is correct
12	Correct	50 ms	33476 KB	Output is correct
13	Correct	55 ms	33888 KB	Output is correct
14	Correct	50 ms	34400 KB	Output is correct
15	Correct	5 ms	26972 KB	Output is correct
16	Correct	5 ms	27224 KB	Output is correct
17	Correct	5 ms	26972 KB	Output is correct
18	Correct	5 ms	26716 KB	Output is correct
19	Correct	5 ms	26868 KB	Output is correct
20	Correct	5 ms	26972 KB	Output is correct
21	Correct	5 ms	26972 KB	Output is correct
22	Correct	5 ms	26716 KB	Output is correct
23	Correct	5 ms	26972 KB	Output is correct
24	Correct	5 ms	26716 KB	Output is correct
25	Correct	5 ms	26972 KB	Output is correct
26	Correct	5 ms	26972 KB	Output is correct
27	Correct	5 ms	26972 KB	Output is correct
28	Correct	6 ms	26716 KB	Output is correct
29	Correct	5 ms	26972 KB	Output is correct
30	Correct	5 ms	26968 KB	Output is correct
31	Correct	5 ms	27016 KB	Output is correct
32	Correct	5 ms	26864 KB	Output is correct
33	Correct	5 ms	26972 KB	Output is correct
34	Correct	12 ms	27928 KB	Output is correct
35	Correct	62 ms	36452 KB	Output is correct
36	Correct	65 ms	35784 KB	Output is correct
37	Correct	70 ms	35524 KB	Output is correct
38	Correct	58 ms	35356 KB	Output is correct
39	Correct	64 ms	35012 KB	Output is correct
40	Correct	62 ms	34244 KB	Output is correct
41	Correct	59 ms	36576 KB	Output is correct
42	Correct	64 ms	36684 KB	Output is correct
43	Correct	46 ms	32964 KB	Output is correct
44	Correct	60 ms	35016 KB	Output is correct
45	Correct	80 ms	37308 KB	Output is correct
46	Correct	59 ms	36036 KB	Output is correct
47	Correct	71 ms	36204 KB	Output is correct
48	Correct	65 ms	35784 KB	Output is correct
49	Correct	60 ms	36104 KB	Output is correct
50	Correct	48 ms	33584 KB	Output is correct
51	Correct	69 ms	35780 KB	Output is correct
52	Correct	96 ms	40700 KB	Output is correct
53	Correct	102 ms	40244 KB	Output is correct
54	Correct	107 ms	42688 KB	Output is correct
55	Correct	48 ms	32968 KB	Output is correct
56	Correct	94 ms	39648 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	22620 KB	Output is correct
2	Correct	4 ms	22620 KB	Output is correct
3	Correct	4 ms	22872 KB	Output is correct
4	Correct	5 ms	22620 KB	Output is correct
5	Correct	4 ms	22880 KB	Output is correct
6	Correct	4 ms	22872 KB	Output is correct
7	Correct	4 ms	22876 KB	Output is correct
8	Correct	4 ms	22876 KB	Output is correct
9	Correct	48 ms	32200 KB	Output is correct
10	Correct	59 ms	33768 KB	Output is correct
11	Correct	50 ms	33476 KB	Output is correct
12	Correct	55 ms	33888 KB	Output is correct
13	Correct	50 ms	34400 KB	Output is correct
14	Correct	45 ms	32456 KB	Output is correct
15	Correct	89 ms	37576 KB	Output is correct
16	Correct	88 ms	37320 KB	Output is correct
17	Correct	91 ms	37980 KB	Output is correct
18	Correct	89 ms	38296 KB	Output is correct
19	Correct	206 ms	37564 KB	Output is correct
20	Correct	171 ms	37380 KB	Output is correct
21	Correct	166 ms	37612 KB	Output is correct
22	Correct	178 ms	37208 KB	Output is correct
23	Correct	174 ms	37568 KB	Output is correct
24	Correct	240 ms	37408 KB	Output is correct
25	Correct	168 ms	37312 KB	Output is correct
26	Correct	160 ms	37348 KB	Output is correct
27	Correct	5 ms	26972 KB	Output is correct
28	Correct	5 ms	27224 KB	Output is correct
29	Correct	5 ms	26972 KB	Output is correct
30	Correct	5 ms	26716 KB	Output is correct
31	Correct	5 ms	26868 KB	Output is correct
32	Correct	5 ms	26972 KB	Output is correct
33	Correct	5 ms	26972 KB	Output is correct
34	Correct	5 ms	26716 KB	Output is correct
35	Correct	5 ms	26972 KB	Output is correct
36	Correct	12 ms	27928 KB	Output is correct
37	Correct	62 ms	36452 KB	Output is correct
38	Correct	65 ms	35784 KB	Output is correct
39	Correct	70 ms	35524 KB	Output is correct
40	Correct	58 ms	35356 KB	Output is correct
41	Correct	64 ms	35012 KB	Output is correct
42	Correct	62 ms	34244 KB	Output is correct
43	Correct	59 ms	36576 KB	Output is correct
44	Correct	64 ms	36684 KB	Output is correct
45	Correct	46 ms	32964 KB	Output is correct
46	Correct	60 ms	35016 KB	Output is correct
47	Correct	18 ms	28292 KB	Output is correct
48	Correct	238 ms	40804 KB	Output is correct
49	Correct	185 ms	39624 KB	Output is correct
50	Correct	168 ms	39536 KB	Output is correct
51	Correct	241 ms	39336 KB	Output is correct
52	Correct	145 ms	38756 KB	Output is correct
53	Correct	122 ms	37320 KB	Output is correct
54	Correct	194 ms	40852 KB	Output is correct
55	Correct	227 ms	40648 KB	Output is correct
56	Correct	227 ms	36724 KB	Output is correct
57	Correct	156 ms	39360 KB	Output is correct

Subtask #6

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	26716 KB	Output is correct
2	Correct	5 ms	22620 KB	Output is correct
3	Correct	4 ms	22620 KB	Output is correct
4	Correct	4 ms	22872 KB	Output is correct
5	Correct	5 ms	22620 KB	Output is correct
6	Correct	4 ms	22880 KB	Output is correct
7	Correct	4 ms	22872 KB	Output is correct
8	Correct	4 ms	22876 KB	Output is correct
9	Correct	4 ms	22876 KB	Output is correct
10	Correct	48 ms	32200 KB	Output is correct
11	Correct	59 ms	33768 KB	Output is correct
12	Correct	50 ms	33476 KB	Output is correct
13	Correct	55 ms	33888 KB	Output is correct
14	Correct	50 ms	34400 KB	Output is correct
15	Correct	45 ms	32456 KB	Output is correct
16	Correct	89 ms	37576 KB	Output is correct
17	Correct	88 ms	37320 KB	Output is correct
18	Correct	91 ms	37980 KB	Output is correct
19	Correct	89 ms	38296 KB	Output is correct
20	Correct	206 ms	37564 KB	Output is correct
21	Correct	171 ms	37380 KB	Output is correct
22	Correct	166 ms	37612 KB	Output is correct
23	Correct	178 ms	37208 KB	Output is correct
24	Correct	174 ms	37568 KB	Output is correct
25	Correct	240 ms	37408 KB	Output is correct
26	Correct	168 ms	37312 KB	Output is correct
27	Correct	160 ms	37348 KB	Output is correct
28	Correct	5 ms	26972 KB	Output is correct
29	Correct	5 ms	27224 KB	Output is correct
30	Correct	5 ms	26972 KB	Output is correct
31	Correct	5 ms	26716 KB	Output is correct
32	Correct	5 ms	26868 KB	Output is correct
33	Correct	5 ms	26972 KB	Output is correct
34	Correct	5 ms	26972 KB	Output is correct
35	Correct	5 ms	26716 KB	Output is correct
36	Correct	5 ms	26972 KB	Output is correct
37	Correct	12 ms	27928 KB	Output is correct
38	Correct	62 ms	36452 KB	Output is correct
39	Correct	65 ms	35784 KB	Output is correct
40	Correct	70 ms	35524 KB	Output is correct
41	Correct	58 ms	35356 KB	Output is correct
42	Correct	64 ms	35012 KB	Output is correct
43	Correct	62 ms	34244 KB	Output is correct
44	Correct	59 ms	36576 KB	Output is correct
45	Correct	64 ms	36684 KB	Output is correct
46	Correct	46 ms	32964 KB	Output is correct
47	Correct	60 ms	35016 KB	Output is correct
48	Correct	18 ms	28292 KB	Output is correct
49	Correct	238 ms	40804 KB	Output is correct
50	Correct	185 ms	39624 KB	Output is correct
51	Correct	168 ms	39536 KB	Output is correct
52	Correct	241 ms	39336 KB	Output is correct
53	Correct	145 ms	38756 KB	Output is correct
54	Correct	122 ms	37320 KB	Output is correct
55	Correct	194 ms	40852 KB	Output is correct
56	Correct	227 ms	40648 KB	Output is correct
57	Correct	227 ms	36724 KB	Output is correct
58	Correct	156 ms	39360 KB	Output is correct
59	Correct	69 ms	33368 KB	Output is correct
60	Correct	211 ms	40764 KB	Output is correct
61	Correct	181 ms	40828 KB	Output is correct
62	Correct	205 ms	41376 KB	Output is correct
63	Correct	190 ms	41360 KB	Output is correct
64	Correct	5 ms	26716 KB	Output is correct
65	Correct	5 ms	26972 KB	Output is correct
66	Correct	5 ms	26972 KB	Output is correct
67	Correct	5 ms	26972 KB	Output is correct
68	Correct	6 ms	26716 KB	Output is correct
69	Correct	5 ms	26972 KB	Output is correct
70	Correct	5 ms	26968 KB	Output is correct
71	Correct	5 ms	27016 KB	Output is correct
72	Correct	5 ms	26864 KB	Output is correct
73	Correct	5 ms	26972 KB	Output is correct
74	Correct	80 ms	37308 KB	Output is correct
75	Correct	59 ms	36036 KB	Output is correct
76	Correct	71 ms	36204 KB	Output is correct
77	Correct	65 ms	35784 KB	Output is correct
78	Correct	60 ms	36104 KB	Output is correct
79	Correct	48 ms	33584 KB	Output is correct
80	Correct	69 ms	35780 KB	Output is correct
81	Correct	96 ms	40700 KB	Output is correct
82	Correct	102 ms	40244 KB	Output is correct
83	Correct	107 ms	42688 KB	Output is correct
84	Correct	48 ms	32968 KB	Output is correct
85	Correct	94 ms	39648 KB	Output is correct
86	Correct	49 ms	31436 KB	Output is correct
87	Correct	188 ms	39876 KB	Output is correct
88	Correct	190 ms	39476 KB	Output is correct
89	Correct	185 ms	39372 KB	Output is correct
90	Correct	132 ms	39104 KB	Output is correct
91	Correct	136 ms	39704 KB	Output is correct
92	Correct	158 ms	39460 KB	Output is correct
93	Correct	221 ms	43280 KB	Output is correct
94	Correct	202 ms	43980 KB	Output is correct
95	Correct	233 ms	46272 KB	Output is correct
96	Correct	185 ms	36724 KB	Output is correct
97	Correct	208 ms	41892 KB	Output is correct