Submission details
Task:Connect cities
Sender:ollipauna
Submission time:2025-09-06 11:09:08 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.86 sdetails
#70.87 sdetails
#80.86 sdetails
#90.86 sdetails
#100.86 sdetails
#110.18 sdetails
#120.00 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < clusters.size() - 1; ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Code

#include<iostream>
#include<queue>
#include <unordered_map>
#include <set>
#include <utility>

typedef long long ll;
using namespace std;


int main()
{   
    ll cities, roads;

    cin >> cities >> roads;

    vector<ll> adj[cities + 1];

    ll a, b;

    while (cin >> a >> b)
    {
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<pair<ll, ll>> pps;

    for (int c = 1; c <= cities; ++c)
    {
        for (const auto b : adj[c])
        {
            cout << c << " - " << b << endl;
        }
    }

    bool visited[cities + 1];
    vector<vector<ll>> clusters;

    for (int c = 1; c <= cities; ++c)
    {
        if (visited[c])
        {
            continue;
        }
        else
        {   
            queue<ll> q;
            q.push(c);
            vector<ll> cluster;
            
            while (!q.empty())
            {
                ll node = q.front();
                q.pop();
                visited[node] = true;
                cluster.push_back(node);

                for (const auto b : adj[node])
                {
                    if (!visited[b])
                    {
                        q.push(b);
                    }
                }
            }

            clusters.push_back(cluster);
        }
    }

    cout << clusters.size() - 1 << std::endl;
    
    for (int i = 0; i < clusters.size() - 1; ++i)
    {
        cout << clusters[i][0] << " " << clusters[i+1][0] << std::endl;
    }


    return 0;
}

Test details

Test 1

Verdict:

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

correct output
2
1 2
2 7

user output
1 - 4
1 - 10
2 - 5
2 - 6
2 - 3
...
Truncated

Test 2

Verdict:

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

correct output
2
1 4
4 5

user output
1 - 9
2 - 7
3 - 9
6 - 8
6 - 9
...
Truncated

Test 3

Verdict:

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

correct output
0

user output
1 - 7
1 - 3
2 - 9
3 - 1
3 - 4
...
Truncated

Test 4

Verdict:

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

correct output
1
1 3

user output
1 - 5
2 - 7
2 - 4
4 - 8
4 - 9
...
Truncated

Test 5

Verdict:

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

correct output
0

user output
1 - 8
1 - 5
2 - 4
3 - 4
4 - 9
...
Truncated

Test 6

Verdict:

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

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

user output
2 - 7715
2 - 60225
4 - 88077
4 - 52040
4 - 26316
...
Truncated

Test 7

Verdict:

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

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

user output
2 - 93165
2 - 92454
2 - 42298
3 - 82946
3 - 62163
...
Truncated

Test 8

Verdict:

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

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

user output
1 - 88823
1 - 52592
2 - 77704
2 - 80021
3 - 87218
...
Truncated

Test 9

Verdict:

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

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

user output
1 - 66686
2 - 25754
2 - 46160
2 - 59959
2 - 37613
...
Truncated

Test 10

Verdict:

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

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

user output
1 - 33404
1 - 46196
1 - 4708
2 - 85319
2 - 4093
...
Truncated

Test 11

Verdict:

input
100000 1
1 2

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

user output
1 - 2
2 - 1
98889
1 3
3 4
...
Truncated

Test 12

Verdict:

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

correct output
2
1 2
2 7

user output
1 - 4
1 - 10
2 - 5
2 - 6
2 - 3
...
Truncated