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