CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:bubu2006
Submission time:2024-09-04 18:54:51 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.05 sdetails
#9ACCEPTED0.05 sdetails
#10ACCEPTED0.06 sdetails
#11ACCEPTED0.05 sdetails
#12ACCEPTED0.00 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() {
cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
const int N = 2e5 + 5;
int n, m;
int par[N], sz[N];
int root(int u) {
return par[u] == u ? u : par[u] = root(par[u]);
}
void unite(int u, int v) {
u = root(u), v = root(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
unite(u, v);
}
set<int> st;
for (int i = 1; i <= n; i++) {
st.insert(root(i));
}
vector<int> v(st.begin(), st.end());
cout << (int)v.size() - 1 << '\n';
for (int i = 0; i + 1 < (int)v.size(); i++) {
cout << v[i] << ' ' << v[i + 1] << '\n';
}
}

Test details

Test 1

Verdict: ACCEPTED

input
10 10
2 5
5 6
1 4
6 8
...

correct output
2
1 2
2 7

user output
2
1 2
2 7

Test 2

Verdict: ACCEPTED

input
10 10
3 9
6 8
9 10
7 8
...

correct output
2
1 4
4 5

user output
2
4 5
5 6

Test 3

Verdict: ACCEPTED

input
10 10
7 9
1 7
1 3
3 4
...

correct output
0

user output
0

Test 4

Verdict: ACCEPTED

input
10 10
4 8
5 9
4 9
2 7
...

correct output
1
1 3

user output
1
3 4

Test 5

Verdict: ACCEPTED

input
10 10
4 9
2 4
7 10
1 8
...

correct output
0

user output
0

Test 6

Verdict: ACCEPTED

input
100000 200000
7233 22146
94937 96203
6133 10731
98737 99193
...

correct output
4785
1 2
2 3
3 4
4 5
...

user output
4785
1 3
3 11
11 14
14 17
...
Truncated

Test 7

Verdict: ACCEPTED

input
100000 200000
92950 93575
24401 88897
41796 99364
47106 50330
...

correct output
4868
1 2
2 7
7 9
9 15
...

user output
4868
1 7
7 9
9 15
15 16
...
Truncated

Test 8

Verdict: ACCEPTED

input
100000 200000
15637 76736
79169 98809
4382 86557
73383 77029
...

correct output
4683
1 9
9 20
20 27
27 28
...

user output
4683
9 20
20 27
27 28
28 33
...
Truncated

Test 9

Verdict: ACCEPTED

input
100000 200000
47932 66981
86401 99942
4353 27841
60492 67345
...

correct output
4807
1 6
6 7
7 11
11 12
...

user output
4807
6 7
7 11
11 12
12 30
...
Truncated

Test 10

Verdict: ACCEPTED

input
100000 200000
6554 44548
76413 98555
5447 59589
70166 74434
...

correct output
4786
1 2
2 18
18 21
21 27
...

user output
4786
18 21
21 27
27 28
28 29
...
Truncated

Test 11

Verdict: ACCEPTED

input
100000 1
1 2

correct output
99998
1 3
3 4
4 5
5 6
...

user output
99998
1 3
3 4
4 5
5 6
...
Truncated

Test 12

Verdict: ACCEPTED

input
10 9
2 5
5 6
1 4
6 8
...

correct output
2
1 2
2 7

user output
2
1 2
2 7