Submission #563729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
563729	2022-05-18T04:10:29 Z	8e7	Swapping Cities (APIO20_swap)	C++17	100 / 100	580 ms	25360 KB

swap

//Challenge: Accepted
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct edge{
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};
vector<pii> ev[maxn]; //events
int valid[maxn];
struct DSU{
	int par[maxn], deg[maxn], siz[maxn];
	bool mark[maxn];
	pii leaf[maxn];
	int ti;
	void init(int n) {
		for (int i = 0;i < n;i++) {
			ev[i].push_back({-1, i});
			siz[i] = 1;
			par[i] = i, deg[i] = 0, mark[i] = 0, leaf[i] = {i, 0}; 
			valid[i] = 1<<30;
		}
		ti = 0;
	}
	int find(int a) {
		if (a == par[a]) return a;
		int ret = find(par[a]);
		if (ret != par[a]) ev[a].push_back({ti, ret});
		par[a] = ret;
		return ret;
	}
	void Union(int a, int b) {
		int pa = find(a), pb = find(b);
		if (siz[pa] > siz[pb]) swap(pa, pb), swap(a, b);
		deg[a]++, deg[b]++;
		if (deg[a] >= 3 || deg[b] >= 3 || mark[pa]) {
			valid[pb] = min(valid[pb], ti);
			mark[pb] = 1;
		}
		if (deg[a] == 1 && deg[b] == 1) {
			leaf[pb] = {a, b};
		} else {
			if (pa == pb && (leaf[pa] == make_pair(a, b) || leaf[pa] == make_pair(b, a))) {
				valid[pb] = min(valid[pb], ti);
				mark[pb] = 1;
			}
			if (pa != pb) {
				pii p;
				if (deg[leaf[pa].ff] == 1) p.ff = leaf[pa].ff;
				else p.ff = leaf[pa].ss;
				if (deg[leaf[pb].ff] == 1) p.ss = leaf[pb].ff;
				else p.ss = leaf[pb].ss;
				leaf[pb] = p;
			}
		}
		if (pa != pb) {
			siz[pb] += siz[pa];
			ev[pa].push_back({ti, pb});
			par[pa] = pb;
		}
	}
} d;
vector<edge> ed;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	for (int i = 0;i < m;i++) ed.push_back(edge(U[i], V[i], W[i]));
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	d.init(n);
	for (int i = 0;i < m;i++) {
		d.Union(ed[i].u, ed[i].v);
		d.ti++;
	}
}
int pfind(int a, int ti) {
	int ind = upper_bound(ev[a].begin(), ev[a].end(), make_pair(ti, 1<<30)) - ev[a].begin() - 1;	
	if (ev[a][ind].ss == a) return a;
	return pfind(ev[a][ind].ss, ti);
}
int getMinimumFuelCapacity(int X, int Y) {
	int low = 0, up = m;
	while (low < up - 1) {
		int mid = (low + up) / 2;
		int vx = pfind(X, mid), vy = pfind(Y, mid);
		if (vx == vy && valid[vx] <= mid) up = mid;
		else low = mid;
	}
	if (up == m) return -1;
	else return ed[up].w;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3540 KB	Output is correct
6	Correct	4 ms	3536 KB	Output is correct
7	Correct	3 ms	3540 KB	Output is correct
8	Correct	4 ms	3512 KB	Output is correct
9	Correct	63 ms	10596 KB	Output is correct
10	Correct	77 ms	12224 KB	Output is correct
11	Correct	76 ms	12092 KB	Output is correct
12	Correct	83 ms	12556 KB	Output is correct
13	Correct	72 ms	11660 KB	Output is correct
14	Correct	100 ms	10816 KB	Output is correct
15	Correct	512 ms	14112 KB	Output is correct
16	Correct	510 ms	13936 KB	Output is correct
17	Correct	537 ms	14364 KB	Output is correct
18	Correct	246 ms	13444 KB	Output is correct
19	Correct	243 ms	8412 KB	Output is correct
20	Correct	485 ms	15312 KB	Output is correct
21	Correct	550 ms	15240 KB	Output is correct
22	Correct	530 ms	15776 KB	Output is correct
23	Correct	251 ms	14856 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	215 ms	14324 KB	Output is correct
4	Correct	241 ms	18380 KB	Output is correct
5	Correct	232 ms	18520 KB	Output is correct
6	Correct	223 ms	18272 KB	Output is correct
7	Correct	234 ms	18608 KB	Output is correct
8	Correct	226 ms	18184 KB	Output is correct
9	Correct	228 ms	18328 KB	Output is correct
10	Correct	226 ms	18124 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3540 KB	Output is correct
6	Correct	4 ms	3536 KB	Output is correct
7	Correct	3 ms	3540 KB	Output is correct
8	Correct	4 ms	3512 KB	Output is correct
9	Correct	2 ms	3412 KB	Output is correct
10	Correct	3 ms	3540 KB	Output is correct
11	Correct	3 ms	3540 KB	Output is correct
12	Correct	2 ms	3540 KB	Output is correct
13	Correct	2 ms	3412 KB	Output is correct
14	Correct	3 ms	3460 KB	Output is correct
15	Correct	3 ms	3540 KB	Output is correct
16	Correct	3 ms	3540 KB	Output is correct
17	Correct	2 ms	3540 KB	Output is correct
18	Correct	3 ms	3540 KB	Output is correct
19	Correct	2 ms	3540 KB	Output is correct
20	Correct	3 ms	3540 KB	Output is correct
21	Correct	3 ms	3540 KB	Output is correct
22	Correct	3 ms	3540 KB	Output is correct
23	Correct	3 ms	3412 KB	Output is correct
24	Correct	3 ms	3540 KB	Output is correct
25	Correct	4 ms	3540 KB	Output is correct
26	Correct	4 ms	3540 KB	Output is correct
27	Correct	2 ms	3540 KB	Output is correct
28	Correct	3 ms	3556 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3412 KB	Output is correct
6	Correct	2 ms	3540 KB	Output is correct
7	Correct	4 ms	3536 KB	Output is correct
8	Correct	3 ms	3540 KB	Output is correct
9	Correct	4 ms	3512 KB	Output is correct
10	Correct	63 ms	10596 KB	Output is correct
11	Correct	77 ms	12224 KB	Output is correct
12	Correct	76 ms	12092 KB	Output is correct
13	Correct	83 ms	12556 KB	Output is correct
14	Correct	72 ms	11660 KB	Output is correct
15	Correct	3 ms	3540 KB	Output is correct
16	Correct	3 ms	3540 KB	Output is correct
17	Correct	2 ms	3540 KB	Output is correct
18	Correct	2 ms	3412 KB	Output is correct
19	Correct	3 ms	3460 KB	Output is correct
20	Correct	3 ms	3540 KB	Output is correct
21	Correct	3 ms	3540 KB	Output is correct
22	Correct	2 ms	3540 KB	Output is correct
23	Correct	3 ms	3540 KB	Output is correct
24	Correct	2 ms	3540 KB	Output is correct
25	Correct	3 ms	3540 KB	Output is correct
26	Correct	3 ms	3540 KB	Output is correct
27	Correct	3 ms	3540 KB	Output is correct
28	Correct	3 ms	3412 KB	Output is correct
29	Correct	3 ms	3540 KB	Output is correct
30	Correct	4 ms	3540 KB	Output is correct
31	Correct	4 ms	3540 KB	Output is correct
32	Correct	2 ms	3540 KB	Output is correct
33	Correct	3 ms	3556 KB	Output is correct
34	Correct	10 ms	4700 KB	Output is correct
35	Correct	88 ms	12564 KB	Output is correct
36	Correct	82 ms	12556 KB	Output is correct
37	Correct	72 ms	12580 KB	Output is correct
38	Correct	72 ms	12436 KB	Output is correct
39	Correct	86 ms	12404 KB	Output is correct
40	Correct	67 ms	11616 KB	Output is correct
41	Correct	82 ms	12608 KB	Output is correct
42	Correct	73 ms	12604 KB	Output is correct
43	Correct	79 ms	11776 KB	Output is correct
44	Correct	79 ms	12544 KB	Output is correct
45	Correct	87 ms	13728 KB	Output is correct
46	Correct	71 ms	12624 KB	Output is correct
47	Correct	74 ms	12640 KB	Output is correct
48	Correct	72 ms	13200 KB	Output is correct
49	Correct	60 ms	10304 KB	Output is correct
50	Correct	48 ms	8184 KB	Output is correct
51	Correct	70 ms	12308 KB	Output is correct
52	Correct	112 ms	16008 KB	Output is correct
53	Correct	104 ms	16276 KB	Output is correct
54	Correct	129 ms	17688 KB	Output is correct
55	Correct	56 ms	11780 KB	Output is correct
56	Correct	103 ms	15940 KB	Output is correct

Subtask #5

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3540 KB	Output is correct
6	Correct	4 ms	3536 KB	Output is correct
7	Correct	3 ms	3540 KB	Output is correct
8	Correct	4 ms	3512 KB	Output is correct
9	Correct	63 ms	10596 KB	Output is correct
10	Correct	77 ms	12224 KB	Output is correct
11	Correct	76 ms	12092 KB	Output is correct
12	Correct	83 ms	12556 KB	Output is correct
13	Correct	72 ms	11660 KB	Output is correct
14	Correct	100 ms	10816 KB	Output is correct
15	Correct	512 ms	14112 KB	Output is correct
16	Correct	510 ms	13936 KB	Output is correct
17	Correct	537 ms	14364 KB	Output is correct
18	Correct	246 ms	13444 KB	Output is correct
19	Correct	215 ms	14324 KB	Output is correct
20	Correct	241 ms	18380 KB	Output is correct
21	Correct	232 ms	18520 KB	Output is correct
22	Correct	223 ms	18272 KB	Output is correct
23	Correct	234 ms	18608 KB	Output is correct
24	Correct	226 ms	18184 KB	Output is correct
25	Correct	228 ms	18328 KB	Output is correct
26	Correct	226 ms	18124 KB	Output is correct
27	Correct	3 ms	3540 KB	Output is correct
28	Correct	3 ms	3540 KB	Output is correct
29	Correct	2 ms	3540 KB	Output is correct
30	Correct	2 ms	3412 KB	Output is correct
31	Correct	3 ms	3460 KB	Output is correct
32	Correct	3 ms	3540 KB	Output is correct
33	Correct	3 ms	3540 KB	Output is correct
34	Correct	2 ms	3540 KB	Output is correct
35	Correct	3 ms	3540 KB	Output is correct
36	Correct	10 ms	4700 KB	Output is correct
37	Correct	88 ms	12564 KB	Output is correct
38	Correct	82 ms	12556 KB	Output is correct
39	Correct	72 ms	12580 KB	Output is correct
40	Correct	72 ms	12436 KB	Output is correct
41	Correct	86 ms	12404 KB	Output is correct
42	Correct	67 ms	11616 KB	Output is correct
43	Correct	82 ms	12608 KB	Output is correct
44	Correct	73 ms	12604 KB	Output is correct
45	Correct	79 ms	11776 KB	Output is correct
46	Correct	79 ms	12544 KB	Output is correct
47	Correct	33 ms	5348 KB	Output is correct
48	Correct	436 ms	19252 KB	Output is correct
49	Correct	424 ms	19380 KB	Output is correct
50	Correct	451 ms	19224 KB	Output is correct
51	Correct	420 ms	19140 KB	Output is correct
52	Correct	396 ms	18808 KB	Output is correct
53	Correct	338 ms	16700 KB	Output is correct
54	Correct	435 ms	20320 KB	Output is correct
55	Correct	443 ms	19396 KB	Output is correct
56	Correct	212 ms	18396 KB	Output is correct
57	Correct	376 ms	20116 KB	Output is correct

Subtask #6

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3412 KB	Output is correct
4	Correct	2 ms	3412 KB	Output is correct
5	Correct	2 ms	3412 KB	Output is correct
6	Correct	2 ms	3540 KB	Output is correct
7	Correct	4 ms	3536 KB	Output is correct
8	Correct	3 ms	3540 KB	Output is correct
9	Correct	4 ms	3512 KB	Output is correct
10	Correct	63 ms	10596 KB	Output is correct
11	Correct	77 ms	12224 KB	Output is correct
12	Correct	76 ms	12092 KB	Output is correct
13	Correct	83 ms	12556 KB	Output is correct
14	Correct	72 ms	11660 KB	Output is correct
15	Correct	100 ms	10816 KB	Output is correct
16	Correct	512 ms	14112 KB	Output is correct
17	Correct	510 ms	13936 KB	Output is correct
18	Correct	537 ms	14364 KB	Output is correct
19	Correct	246 ms	13444 KB	Output is correct
20	Correct	215 ms	14324 KB	Output is correct
21	Correct	241 ms	18380 KB	Output is correct
22	Correct	232 ms	18520 KB	Output is correct
23	Correct	223 ms	18272 KB	Output is correct
24	Correct	234 ms	18608 KB	Output is correct
25	Correct	226 ms	18184 KB	Output is correct
26	Correct	228 ms	18328 KB	Output is correct
27	Correct	226 ms	18124 KB	Output is correct
28	Correct	3 ms	3540 KB	Output is correct
29	Correct	3 ms	3540 KB	Output is correct
30	Correct	2 ms	3540 KB	Output is correct
31	Correct	2 ms	3412 KB	Output is correct
32	Correct	3 ms	3460 KB	Output is correct
33	Correct	3 ms	3540 KB	Output is correct
34	Correct	3 ms	3540 KB	Output is correct
35	Correct	2 ms	3540 KB	Output is correct
36	Correct	3 ms	3540 KB	Output is correct
37	Correct	10 ms	4700 KB	Output is correct
38	Correct	88 ms	12564 KB	Output is correct
39	Correct	82 ms	12556 KB	Output is correct
40	Correct	72 ms	12580 KB	Output is correct
41	Correct	72 ms	12436 KB	Output is correct
42	Correct	86 ms	12404 KB	Output is correct
43	Correct	67 ms	11616 KB	Output is correct
44	Correct	82 ms	12608 KB	Output is correct
45	Correct	73 ms	12604 KB	Output is correct
46	Correct	79 ms	11776 KB	Output is correct
47	Correct	79 ms	12544 KB	Output is correct
48	Correct	33 ms	5348 KB	Output is correct
49	Correct	436 ms	19252 KB	Output is correct
50	Correct	424 ms	19380 KB	Output is correct
51	Correct	451 ms	19224 KB	Output is correct
52	Correct	420 ms	19140 KB	Output is correct
53	Correct	396 ms	18808 KB	Output is correct
54	Correct	338 ms	16700 KB	Output is correct
55	Correct	435 ms	20320 KB	Output is correct
56	Correct	443 ms	19396 KB	Output is correct
57	Correct	212 ms	18396 KB	Output is correct
58	Correct	376 ms	20116 KB	Output is correct
59	Correct	243 ms	8412 KB	Output is correct
60	Correct	485 ms	15312 KB	Output is correct
61	Correct	550 ms	15240 KB	Output is correct
62	Correct	530 ms	15776 KB	Output is correct
63	Correct	251 ms	14856 KB	Output is correct
64	Correct	2 ms	3540 KB	Output is correct
65	Correct	3 ms	3540 KB	Output is correct
66	Correct	3 ms	3540 KB	Output is correct
67	Correct	3 ms	3540 KB	Output is correct
68	Correct	3 ms	3412 KB	Output is correct
69	Correct	3 ms	3540 KB	Output is correct
70	Correct	4 ms	3540 KB	Output is correct
71	Correct	4 ms	3540 KB	Output is correct
72	Correct	2 ms	3540 KB	Output is correct
73	Correct	3 ms	3556 KB	Output is correct
74	Correct	87 ms	13728 KB	Output is correct
75	Correct	71 ms	12624 KB	Output is correct
76	Correct	74 ms	12640 KB	Output is correct
77	Correct	72 ms	13200 KB	Output is correct
78	Correct	60 ms	10304 KB	Output is correct
79	Correct	48 ms	8184 KB	Output is correct
80	Correct	70 ms	12308 KB	Output is correct
81	Correct	112 ms	16008 KB	Output is correct
82	Correct	104 ms	16276 KB	Output is correct
83	Correct	129 ms	17688 KB	Output is correct
84	Correct	56 ms	11780 KB	Output is correct
85	Correct	103 ms	15940 KB	Output is correct
86	Correct	78 ms	9388 KB	Output is correct
87	Correct	422 ms	19260 KB	Output is correct
88	Correct	438 ms	19392 KB	Output is correct
89	Correct	290 ms	19416 KB	Output is correct
90	Correct	235 ms	16888 KB	Output is correct
91	Correct	235 ms	16688 KB	Output is correct
92	Correct	273 ms	19672 KB	Output is correct
93	Correct	475 ms	24148 KB	Output is correct
94	Correct	375 ms	24604 KB	Output is correct
95	Correct	580 ms	25360 KB	Output is correct
96	Correct	217 ms	18536 KB	Output is correct
97	Correct	331 ms	22596 KB	Output is correct