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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:55:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   55 |     printf("%d\n", ans.size()-1);
      |             ~^     ~~~~~~~~~~~~
      |              |               |
      |              int             std::set<int>::size_type {aka long unsigned int}
      |             %ld
input/code.cpp: In function 'void Test()':
input/code.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("temp\\in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~...

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
typedef long long LL;
const int N=100005;
// Union&Find Start
int father[N], size[N];
int Find(int x)
{
if(father[x]==x)
return x;
return father[x]=Find(father[x]);
}
void Union(int x, int y)
{
x = Find(x), y=Find(y);
if(x==y)
return;
if(size[x] < size[y])
std::swap(x, y);
father[y] = x;
size[x] += size[y];
}
// Union&Find End
void Test()
{
freopen("temp\\in.txt", "r", stdin);
}
int main()
{
// Test();
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
father[i]=i;
for(int i=1; i<=m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
Union(a, b);
}
std::set<int> ans;
for(int i=1; i<=n; i++)
ans.insert(Find(i));
// P
printf("%d\n", ans.size()-1);
int last = *ans.begin();
for(auto it=ans.begin(); it!=ans.end(); it++)
{
if(it==ans.begin())
continue;
int now = *it;
printf("%d %d\n", last, now);
last = now;
}
return 0;
}

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 3
3 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
2 4
4 5

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 6

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 3
3 7