답안 #1048524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048524	2024-08-08T08:07:05 Z	European Bad Bitch(#11090)	Make them Meet (EGOI24_makethemmeet)	C++17	29.2166 / 100	91 ms	14868 KB

Main

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
const int MAXN = 105;

struct disj {
	vector<int> pa;
	void init(int n) {
		pa.clear();
		pa.resize(n);
		iota(all(pa), 0);
	}
	int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
	bool uni(int p, int q) {
		p = find(p);
		q = find(q);
		if (p == q)
			return 0;
		pa[q] = p;
		return 1;
	}
} disj;

int n;
vector<int> gph[MAXN];
vector<vector<int>> seqs;

void swab(int u, int v) {
	vector<int> a(n);
	iota(all(a), 0);
	a[v] = u;
	seqs.push_back(a);
}

void dfs(int x, int p) {
	for (auto &y : gph[x]) {
		if (y == p)
			continue;
		swab(x, y);
		dfs(y, x);
		swab(x, y);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int m;
	cin >> n >> m;
	disj.init(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (disj.uni(u, v)) {
			gph[u].push_back(v);
			gph[v].push_back(u);
		}
	}
	for (int i = 0; i < n; i++)
		dfs(i, -1);
	cout << sz(seqs) << "\n";
	for (auto &v : seqs) {
		for (auto &w : v)
			cout << w << " ";
		cout << "\n";
	}
}

Subtask #1
2.921658986 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Partially correct	76 ms	14288 KB	Partially correct
5	Partially correct	75 ms	14608 KB	Partially correct

Subtask #2
3.7981566818 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Partially correct	2 ms	860 KB	Partially correct
7	Partially correct	5 ms	1408 KB	Partially correct
8	Partially correct	10 ms	2140 KB	Partially correct
9	Partially correct	77 ms	14596 KB	Partially correct

Subtask #3
3.2138248846 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Partially correct	10 ms	1948 KB	Partially correct
5	Partially correct	76 ms	14352 KB	Partially correct
6	Partially correct	79 ms	14520 KB	Partially correct
7	Partially correct	20 ms	4188 KB	Partially correct

Subtask #4
10.5179723496 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Partially correct	76 ms	14288 KB	Partially correct
5	Partially correct	75 ms	14608 KB	Partially correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Partially correct	10 ms	1948 KB	Partially correct
10	Partially correct	76 ms	14352 KB	Partially correct
11	Partially correct	79 ms	14520 KB	Partially correct
12	Partially correct	20 ms	4188 KB	Partially correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Partially correct	75 ms	14184 KB	Partially correct
17	Partially correct	77 ms	14720 KB	Partially correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Partially correct	9 ms	2140 KB	Partially correct
21	Partially correct	74 ms	14344 KB	Partially correct
22	Partially correct	75 ms	14604 KB	Partially correct
23	Partially correct	20 ms	4184 KB	Partially correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Partially correct	76 ms	14668 KB	Partially correct
28	Partially correct	76 ms	14604 KB	Partially correct
29	Partially correct	75 ms	14552 KB	Partially correct
30	Partially correct	76 ms	14668 KB	Partially correct
31	Partially correct	76 ms	14560 KB	Partially correct
32	Partially correct	75 ms	14704 KB	Partially correct
33	Partially correct	83 ms	14868 KB	Partially correct
34	Partially correct	76 ms	14604 KB	Partially correct
35	Partially correct	88 ms	14684 KB	Partially correct
36	Partially correct	75 ms	14684 KB	Partially correct
37	Partially correct	76 ms	14600 KB	Partially correct
38	Partially correct	81 ms	14544 KB	Partially correct
39	Partially correct	75 ms	14624 KB	Partially correct
40	Partially correct	76 ms	14596 KB	Partially correct
41	Partially correct	75 ms	14596 KB	Partially correct
42	Partially correct	76 ms	14736 KB	Partially correct
43	Partially correct	85 ms	14596 KB	Partially correct
44	Partially correct	76 ms	14616 KB	Partially correct
45	Partially correct	77 ms	14532 KB	Partially correct
46	Correct	1 ms	348 KB	Output is correct
47	Correct	0 ms	344 KB	Output is correct
48	Correct	0 ms	348 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	0 ms	348 KB	Output is correct
52	Correct	0 ms	348 KB	Output is correct
53	Correct	0 ms	348 KB	Output is correct
54	Correct	0 ms	348 KB	Output is correct
55	Correct	0 ms	344 KB	Output is correct
56	Correct	0 ms	348 KB	Output is correct
57	Correct	0 ms	348 KB	Output is correct
58	Correct	0 ms	344 KB	Output is correct
59	Correct	0 ms	348 KB	Output is correct
60	Correct	1 ms	348 KB	Output is correct
61	Correct	0 ms	348 KB	Output is correct
62	Correct	0 ms	348 KB	Output is correct
63	Correct	0 ms	348 KB	Output is correct
64	Correct	0 ms	348 KB	Output is correct
65	Correct	0 ms	348 KB	Output is correct

Subtask #5
8.764976958 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Partially correct	76 ms	14288 KB	Partially correct
5	Partially correct	75 ms	14608 KB	Partially correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Partially correct	2 ms	860 KB	Partially correct
12	Partially correct	5 ms	1408 KB	Partially correct
13	Partially correct	10 ms	2140 KB	Partially correct
14	Partially correct	77 ms	14596 KB	Partially correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Partially correct	10 ms	1948 KB	Partially correct
19	Partially correct	76 ms	14352 KB	Partially correct
20	Partially correct	79 ms	14520 KB	Partially correct
21	Partially correct	20 ms	4188 KB	Partially correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Partially correct	75 ms	14184 KB	Partially correct
26	Partially correct	77 ms	14720 KB	Partially correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Partially correct	9 ms	2140 KB	Partially correct
30	Partially correct	74 ms	14344 KB	Partially correct
31	Partially correct	75 ms	14604 KB	Partially correct
32	Partially correct	20 ms	4184 KB	Partially correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Partially correct	76 ms	14668 KB	Partially correct
37	Partially correct	76 ms	14604 KB	Partially correct
38	Partially correct	75 ms	14552 KB	Partially correct
39	Partially correct	76 ms	14668 KB	Partially correct
40	Partially correct	76 ms	14560 KB	Partially correct
41	Partially correct	75 ms	14704 KB	Partially correct
42	Partially correct	83 ms	14868 KB	Partially correct
43	Partially correct	76 ms	14604 KB	Partially correct
44	Partially correct	88 ms	14684 KB	Partially correct
45	Partially correct	75 ms	14684 KB	Partially correct
46	Partially correct	76 ms	14600 KB	Partially correct
47	Partially correct	81 ms	14544 KB	Partially correct
48	Partially correct	75 ms	14624 KB	Partially correct
49	Partially correct	76 ms	14596 KB	Partially correct
50	Partially correct	75 ms	14596 KB	Partially correct
51	Partially correct	76 ms	14736 KB	Partially correct
52	Partially correct	85 ms	14596 KB	Partially correct
53	Partially correct	76 ms	14616 KB	Partially correct
54	Partially correct	77 ms	14532 KB	Partially correct
55	Correct	1 ms	348 KB	Output is correct
56	Correct	0 ms	344 KB	Output is correct
57	Correct	0 ms	348 KB	Output is correct
58	Correct	0 ms	348 KB	Output is correct
59	Correct	0 ms	348 KB	Output is correct
60	Correct	0 ms	348 KB	Output is correct
61	Correct	0 ms	348 KB	Output is correct
62	Correct	0 ms	348 KB	Output is correct
63	Correct	0 ms	348 KB	Output is correct
64	Correct	0 ms	344 KB	Output is correct
65	Correct	0 ms	348 KB	Output is correct
66	Correct	0 ms	348 KB	Output is correct
67	Correct	0 ms	344 KB	Output is correct
68	Correct	0 ms	348 KB	Output is correct
69	Correct	1 ms	348 KB	Output is correct
70	Correct	0 ms	348 KB	Output is correct
71	Correct	0 ms	348 KB	Output is correct
72	Correct	0 ms	348 KB	Output is correct
73	Correct	0 ms	348 KB	Output is correct
74	Correct	0 ms	348 KB	Output is correct
75	Correct	0 ms	348 KB	Output is correct
76	Correct	1 ms	348 KB	Output is correct
77	Correct	1 ms	348 KB	Output is correct
78	Partially correct	82 ms	14412 KB	Partially correct
79	Partially correct	79 ms	14704 KB	Partially correct
80	Correct	0 ms	344 KB	Output is correct
81	Correct	0 ms	348 KB	Output is correct
82	Correct	0 ms	348 KB	Output is correct
83	Correct	1 ms	348 KB	Output is correct
84	Partially correct	2 ms	860 KB	Partially correct
85	Partially correct	5 ms	1372 KB	Partially correct
86	Partially correct	10 ms	2288 KB	Partially correct
87	Partially correct	85 ms	14712 KB	Partially correct
88	Correct	0 ms	348 KB	Output is correct
89	Correct	0 ms	348 KB	Output is correct
90	Partially correct	9 ms	1984 KB	Partially correct
91	Partially correct	73 ms	14300 KB	Partially correct
92	Partially correct	77 ms	14644 KB	Partially correct
93	Partially correct	21 ms	4176 KB	Partially correct
94	Correct	0 ms	344 KB	Output is correct
95	Correct	0 ms	344 KB	Output is correct
96	Correct	0 ms	348 KB	Output is correct
97	Partially correct	75 ms	14760 KB	Partially correct
98	Partially correct	75 ms	14632 KB	Partially correct
99	Partially correct	91 ms	14600 KB	Partially correct
100	Partially correct	79 ms	14620 KB	Partially correct
101	Partially correct	75 ms	14572 KB	Partially correct
102	Partially correct	76 ms	14596 KB	Partially correct
103	Partially correct	75 ms	14600 KB	Partially correct
104	Partially correct	89 ms	14724 KB	Partially correct
105	Partially correct	81 ms	14692 KB	Partially correct
106	Partially correct	75 ms	14692 KB	Partially correct
107	Partially correct	85 ms	14640 KB	Partially correct
108	Partially correct	75 ms	14600 KB	Partially correct
109	Partially correct	82 ms	14600 KB	Partially correct
110	Partially correct	75 ms	14604 KB	Partially correct
111	Partially correct	76 ms	14728 KB	Partially correct
112	Partially correct	84 ms	14804 KB	Partially correct
113	Partially correct	75 ms	14744 KB	Partially correct
114	Partially correct	76 ms	14600 KB	Partially correct
115	Partially correct	75 ms	14596 KB	Partially correct
116	Correct	0 ms	344 KB	Output is correct
117	Correct	0 ms	348 KB	Output is correct
118	Correct	0 ms	348 KB	Output is correct
119	Correct	0 ms	348 KB	Output is correct
120	Correct	0 ms	348 KB	Output is correct
121	Correct	0 ms	348 KB	Output is correct
122	Correct	0 ms	348 KB	Output is correct
123	Correct	0 ms	348 KB	Output is correct
124	Correct	0 ms	348 KB	Output is correct
125	Correct	0 ms	348 KB	Output is correct
126	Correct	0 ms	348 KB	Output is correct
127	Correct	0 ms	348 KB	Output is correct
128	Correct	0 ms	348 KB	Output is correct
129	Correct	0 ms	348 KB	Output is correct
130	Correct	0 ms	344 KB	Output is correct
131	Correct	0 ms	348 KB	Output is correct
132	Correct	0 ms	348 KB	Output is correct
133	Correct	0 ms	348 KB	Output is correct
134	Correct	0 ms	348 KB	Output is correct
135	Correct	0 ms	348 KB	Output is correct
136	Correct	0 ms	348 KB	Output is correct
137	Correct	0 ms	348 KB	Output is correct
138	Correct	1 ms	344 KB	Output is correct
139	Correct	0 ms	348 KB	Output is correct
140	Partially correct	75 ms	14528 KB	Partially correct
141	Correct	0 ms	348 KB	Output is correct
142	Partially correct	81 ms	14568 KB	Partially correct
143	Partially correct	75 ms	14604 KB	Partially correct
144	Partially correct	76 ms	14604 KB	Partially correct
145	Partially correct	83 ms	14600 KB	Partially correct
146	Partially correct	76 ms	14596 KB	Partially correct
147	Partially correct	77 ms	14628 KB	Partially correct
148	Partially correct	75 ms	14604 KB	Partially correct
149	Partially correct	89 ms	14592 KB	Partially correct
150	Partially correct	76 ms	14600 KB	Partially correct
151	Partially correct	75 ms	14592 KB	Partially correct
152	Partially correct	88 ms	14600 KB	Partially correct
153	Partially correct	75 ms	14604 KB	Partially correct
154	Partially correct	75 ms	14600 KB	Partially correct
155	Partially correct	78 ms	14672 KB	Partially correct
156	Partially correct	75 ms	14600 KB	Partially correct
157	Partially correct	79 ms	14600 KB	Partially correct
158	Partially correct	75 ms	14600 KB	Partially correct
159	Partially correct	78 ms	14704 KB	Partially correct
160	Partially correct	75 ms	14604 KB	Partially correct
161	Partially correct	78 ms	14508 KB	Partially correct
162	Correct	0 ms	348 KB	Output is correct
163	Correct	0 ms	348 KB	Output is correct
164	Correct	0 ms	348 KB	Output is correct
165	Correct	0 ms	344 KB	Output is correct

답안 #1048524

Compilation message

Subtask #1 2.921658986 / 10.0

Subtask #2 3.7981566818 / 13.0

Subtask #3 3.2138248846 / 11.0

Subtask #4 10.5179723496 / 36.0

Subtask #5 8.764976958 / 30.0

Subtask #1
2.921658986 / 10.0

Subtask #2
3.7981566818 / 13.0

Subtask #3
3.2138248846 / 11.0

Subtask #4
10.5179723496 / 36.0

Subtask #5
8.764976958 / 30.0