답안 #535974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535974	2022-03-12T02:48:34 Z	dutinmeow	자매 도시 (APIO20_swap)	C++17	53 / 100	2000 ms	35596 KB

swap

#include <bits/stdc++.h>
using namespace std;

//#include "swap.h"

const int LOGN = 19;

vector<int> dep, val;
vector<bool> lin;
vector<array<int, LOGN>> anc;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	vector<tuple<int, int, int>> E(M);
	for (int i = 0; i < M; i++) 
		E[i] = {U[i], V[i], W[i]};
	sort(E.begin(), E.end(), 
		[](const auto &a, const auto &b) {
			return get<2>(a) < get<2>(b);
		}
	);

	struct node { 
		int par, val, siz; bool lin;
		node() = default;
		node(int _par, int _val, int _siz, bool _lin) : par(_par), val(_val), siz(_siz), lin(_lin) {}
	};

	vector<node> T; T.reserve(N + M);
	vector<bool> ep(N);
	vector<int> rt(N);

	for (int i = 0; i < N; i++) {
		T.emplace_back(i, 0, 1, true);
		ep[i] = true;
		rt[i] = i;
	}

	for (auto [u, v, w] : E) {
		while (rt[u] != T[rt[u]].par)
			rt[u] = T[rt[u]].par;
		int up = rt[u];
		while (rt[v] != T[rt[v]].par)
			rt[v] = T[rt[v]].par;
		int vp = rt[v];

		int c = T.size();
		if (up != vp) {
			if (T[up].lin && T[vp].lin && ep[u] && ep[v]) {
				T[up].par = T[vp].par = c;
				T.emplace_back(c, w, T[up].siz + T[vp].siz, true);
				if (T[up].siz > 1)
					ep[u] = false;
				if (T[vp].siz > 1)
					ep[v] = false;
			} else {
				T[up].par = T[vp].par = T.size();
				T.emplace_back(c, w, T[up].siz + T[vp].siz, false);
			}
		} else if (T[up].lin) {
			T[up].par = c;
			T.emplace_back(c, w, T[up].siz + T[vp].siz, false);
		}

		/*
		cout << "edge " << u << ' ' << v << ' ' << w << '\n';
		for (int i = 0; i < T.size(); i++) 
			cout << i << " : " << T[i].par << ' ' << T[i].val << ' ' << (T[i].lin ? "line" : "not line") << '\n';
		cout << '\n';
		*/
	}

	int S = T.size();
	anc.resize(S);
	dep.resize(S);
	val.resize(S);
	lin.resize(S);
	vector<vector<int>> tree(S);
	for (int i = 0; i < S; i++) {
		anc[i][0] = T[i].par;
		val[i] = T[i].val;
		lin[i] = T[i].lin;
		if (i != T[i].par)
			tree[T[i].par].push_back(i);
	}
	for (int k = 1; k < LOGN; k++)
		for (int i = 0; i < S; i++)
			anc[i][k] = anc[anc[i][k - 1]][k - 1];

	const auto dfs = [&](const auto &self, int u) -> void {
		for (int v : tree[u]) {
			dep[v] = dep[u] + 1;
			self(self, v);
		}
	};

	for (int i = 0; i < S; i++) 
		if (i == T[i].par) {
			dep[i] = 0;
			dfs(dfs, i);
		}
}

int getMinimumFuelCapacity(int u, int v) {
	if (dep[u] > dep[v])
		swap(u, v);
	for (int k = LOGN - 1; k >= 0; k--)
		if ((dep[v] - dep[u]) >> k & 1)
			v = anc[v][k];
	//assert(dep[u] == dep[v]);
	if (u != v) {
		for (int k = LOGN - 1; k >= 0; k--)
			if (anc[u][k] != anc[v][k])
				u = anc[u][k], v = anc[v][k];
		u = anc[u][0], v = anc[v][0];
		if (u != v)
			return -1;
	}

	if (!lin[u]) 
		return val[u];
	for (int k = LOGN - 1; k >= 0; k--)
		if (lin[anc[u][k]])
			u = anc[u][k];
	u = anc[u][0];
	if (lin[u]) {
		return -1;
	} else {
		return val[u];
	}
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	85 ms	24908 KB	Output is correct
10	Correct	115 ms	30412 KB	Output is correct
11	Correct	116 ms	29824 KB	Output is correct
12	Correct	115 ms	31616 KB	Output is correct
13	Correct	109 ms	32932 KB	Output is correct
14	Correct	103 ms	24916 KB	Output is correct
15	Correct	238 ms	32164 KB	Output is correct
16	Correct	237 ms	31308 KB	Output is correct
17	Correct	252 ms	33100 KB	Output is correct
18	Correct	314 ms	34508 KB	Output is correct
19	Correct	81 ms	7100 KB	Output is correct
20	Correct	237 ms	32208 KB	Output is correct
21	Correct	219 ms	30968 KB	Output is correct
22	Correct	242 ms	33224 KB	Output is correct
23	Correct	364 ms	34520 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	270 ms	33868 KB	Output is correct
4	Correct	260 ms	35596 KB	Output is correct
5	Correct	273 ms	34476 KB	Output is correct
6	Correct	264 ms	35448 KB	Output is correct
7	Correct	296 ms	34968 KB	Output is correct
8	Correct	276 ms	33640 KB	Output is correct
9	Correct	267 ms	34764 KB	Output is correct
10	Correct	262 ms	33260 KB	Output is correct

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	596 KB	Output is correct
12	Correct	1 ms	596 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	596 KB	Output is correct
16	Correct	1 ms	596 KB	Output is correct
17	Correct	1 ms	596 KB	Output is correct
18	Correct	1 ms	596 KB	Output is correct
19	Correct	1 ms	468 KB	Output is correct
20	Correct	1 ms	596 KB	Output is correct
21	Correct	1 ms	596 KB	Output is correct
22	Correct	1 ms	420 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	596 KB	Output is correct
25	Correct	1 ms	596 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	1 ms	596 KB	Output is correct
28	Correct	2 ms	596 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	85 ms	24908 KB	Output is correct
11	Correct	115 ms	30412 KB	Output is correct
12	Correct	116 ms	29824 KB	Output is correct
13	Correct	115 ms	31616 KB	Output is correct
14	Correct	109 ms	32932 KB	Output is correct
15	Correct	1 ms	596 KB	Output is correct
16	Correct	1 ms	596 KB	Output is correct
17	Correct	1 ms	596 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	468 KB	Output is correct
20	Correct	1 ms	596 KB	Output is correct
21	Correct	1 ms	596 KB	Output is correct
22	Correct	1 ms	596 KB	Output is correct
23	Correct	1 ms	596 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	596 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	1 ms	420 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	596 KB	Output is correct
30	Correct	1 ms	596 KB	Output is correct
31	Correct	1 ms	596 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	2 ms	596 KB	Output is correct
34	Correct	11 ms	4564 KB	Output is correct
35	Correct	112 ms	31544 KB	Output is correct
36	Correct	115 ms	31640 KB	Output is correct
37	Correct	116 ms	31620 KB	Output is correct
38	Correct	112 ms	31168 KB	Output is correct
39	Correct	121 ms	30924 KB	Output is correct
40	Correct	102 ms	28356 KB	Output is correct
41	Correct	114 ms	31632 KB	Output is correct
42	Correct	123 ms	31644 KB	Output is correct
43	Correct	113 ms	33476 KB	Output is correct
44	Correct	121 ms	31676 KB	Output is correct
45	Execution timed out	2071 ms	8392 KB	Time limit exceeded
46	Halted	0 ms	0 KB	-

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	85 ms	24908 KB	Output is correct
10	Correct	115 ms	30412 KB	Output is correct
11	Correct	116 ms	29824 KB	Output is correct
12	Correct	115 ms	31616 KB	Output is correct
13	Correct	109 ms	32932 KB	Output is correct
14	Correct	103 ms	24916 KB	Output is correct
15	Correct	238 ms	32164 KB	Output is correct
16	Correct	237 ms	31308 KB	Output is correct
17	Correct	252 ms	33100 KB	Output is correct
18	Correct	314 ms	34508 KB	Output is correct
19	Correct	270 ms	33868 KB	Output is correct
20	Correct	260 ms	35596 KB	Output is correct
21	Correct	273 ms	34476 KB	Output is correct
22	Correct	264 ms	35448 KB	Output is correct
23	Correct	296 ms	34968 KB	Output is correct
24	Correct	276 ms	33640 KB	Output is correct
25	Correct	267 ms	34764 KB	Output is correct
26	Correct	262 ms	33260 KB	Output is correct
27	Correct	1 ms	596 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	1 ms	596 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	1 ms	596 KB	Output is correct
34	Correct	1 ms	596 KB	Output is correct
35	Correct	1 ms	596 KB	Output is correct
36	Correct	11 ms	4564 KB	Output is correct
37	Correct	112 ms	31544 KB	Output is correct
38	Correct	115 ms	31640 KB	Output is correct
39	Correct	116 ms	31620 KB	Output is correct
40	Correct	112 ms	31168 KB	Output is correct
41	Correct	121 ms	30924 KB	Output is correct
42	Correct	102 ms	28356 KB	Output is correct
43	Correct	114 ms	31632 KB	Output is correct
44	Correct	123 ms	31644 KB	Output is correct
45	Correct	113 ms	33476 KB	Output is correct
46	Correct	121 ms	31676 KB	Output is correct
47	Correct	20 ms	4308 KB	Output is correct
48	Correct	224 ms	33220 KB	Output is correct
49	Correct	233 ms	33236 KB	Output is correct
50	Correct	223 ms	33116 KB	Output is correct
51	Correct	217 ms	32956 KB	Output is correct
52	Correct	212 ms	31124 KB	Output is correct
53	Correct	165 ms	22604 KB	Output is correct
54	Correct	241 ms	33228 KB	Output is correct
55	Correct	220 ms	33116 KB	Output is correct
56	Correct	291 ms	34624 KB	Output is correct
57	Correct	230 ms	33224 KB	Output is correct

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	85 ms	24908 KB	Output is correct
11	Correct	115 ms	30412 KB	Output is correct
12	Correct	116 ms	29824 KB	Output is correct
13	Correct	115 ms	31616 KB	Output is correct
14	Correct	109 ms	32932 KB	Output is correct
15	Correct	103 ms	24916 KB	Output is correct
16	Correct	238 ms	32164 KB	Output is correct
17	Correct	237 ms	31308 KB	Output is correct
18	Correct	252 ms	33100 KB	Output is correct
19	Correct	314 ms	34508 KB	Output is correct
20	Correct	270 ms	33868 KB	Output is correct
21	Correct	260 ms	35596 KB	Output is correct
22	Correct	273 ms	34476 KB	Output is correct
23	Correct	264 ms	35448 KB	Output is correct
24	Correct	296 ms	34968 KB	Output is correct
25	Correct	276 ms	33640 KB	Output is correct
26	Correct	267 ms	34764 KB	Output is correct
27	Correct	262 ms	33260 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	1 ms	596 KB	Output is correct
30	Correct	1 ms	596 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct
33	Correct	1 ms	596 KB	Output is correct
34	Correct	1 ms	596 KB	Output is correct
35	Correct	1 ms	596 KB	Output is correct
36	Correct	1 ms	596 KB	Output is correct
37	Correct	11 ms	4564 KB	Output is correct
38	Correct	112 ms	31544 KB	Output is correct
39	Correct	115 ms	31640 KB	Output is correct
40	Correct	116 ms	31620 KB	Output is correct
41	Correct	112 ms	31168 KB	Output is correct
42	Correct	121 ms	30924 KB	Output is correct
43	Correct	102 ms	28356 KB	Output is correct
44	Correct	114 ms	31632 KB	Output is correct
45	Correct	123 ms	31644 KB	Output is correct
46	Correct	113 ms	33476 KB	Output is correct
47	Correct	121 ms	31676 KB	Output is correct
48	Correct	20 ms	4308 KB	Output is correct
49	Correct	224 ms	33220 KB	Output is correct
50	Correct	233 ms	33236 KB	Output is correct
51	Correct	223 ms	33116 KB	Output is correct
52	Correct	217 ms	32956 KB	Output is correct
53	Correct	212 ms	31124 KB	Output is correct
54	Correct	165 ms	22604 KB	Output is correct
55	Correct	241 ms	33228 KB	Output is correct
56	Correct	220 ms	33116 KB	Output is correct
57	Correct	291 ms	34624 KB	Output is correct
58	Correct	230 ms	33224 KB	Output is correct
59	Correct	81 ms	7100 KB	Output is correct
60	Correct	237 ms	32208 KB	Output is correct
61	Correct	219 ms	30968 KB	Output is correct
62	Correct	242 ms	33224 KB	Output is correct
63	Correct	364 ms	34520 KB	Output is correct
64	Correct	1 ms	468 KB	Output is correct
65	Correct	1 ms	596 KB	Output is correct
66	Correct	1 ms	596 KB	Output is correct
67	Correct	1 ms	420 KB	Output is correct
68	Correct	1 ms	468 KB	Output is correct
69	Correct	1 ms	596 KB	Output is correct
70	Correct	1 ms	596 KB	Output is correct
71	Correct	1 ms	596 KB	Output is correct
72	Correct	1 ms	596 KB	Output is correct
73	Correct	2 ms	596 KB	Output is correct
74	Execution timed out	2071 ms	8392 KB	Time limit exceeded
75	Halted	0 ms	0 KB	-

답안 #535974

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 17.0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 23.0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
17.0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
23.0 / 23.0

Subtask #6
0 / 27.0