Submission details
Task:Fragile network
Sender:aalto25f_006
Submission time:2025-10-08 17:26:42 +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.01 sdetails
#70.09 sdetails
#80.03 sdetails
#90.10 sdetails
#100.05 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.01 sdetails
#150.00 sdetails
#160.00 sdetails
#170.00 sdetails
#180.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails

Compiler report

input/code.cpp: In function 'void alg(std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&)':
input/code.cpp:15:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (!q.empty() or assigned < team.size()) {
      |                          ~~~~~~~~~^~~~~~~~~~~~~
input/code.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             while (i < team.size() and team[i] != 0)
      |                    ~~^~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void alg(vector<int> &team, vector<vector<pair<int, int>>> &adj) {

    queue<int> q;
    q.push(0);
    team[0] = 1;
    int i = 1;
    int assigned = 1;

    while (!q.empty() or assigned < team.size()) {
        if (q.empty()) {
            while (i < team.size() and team[i] != 0)
                ++i;
            q.push(i);
            team[i] = 1;
            ++assigned;
        }
        int node = q.front();
        q.pop();

        for (auto [neighbour, type] : adj[node]) {
            if (team[neighbour] == 0) {
                if (type == 1)
                    team[neighbour] = team[node];
                else 
                    team[neighbour] = 3 - team[node];
                ++assigned;
                q.push(neighbour);
            }
            else {
                if (type == 1 and team[neighbour] != team[node]) {
                    cout << "No" << endl;
                    return;
                }
                else if (type == -1 and team[neighbour] == team[node]) {
                    cout << "No" << endl;
                    return;
                }
            }                
        }
    }
    cout << "Yes" << endl;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n);
    vector<int> team(n, 0);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a-1].push_back({b-1, c});
        adj[b-1].push_back({a-1, c});
    }

    alg(team, adj);
}

Test details

Test 1

Verdict:

input
10
1 5
1 7
1 8
1 3
...

correct output
5
5 2
7 9
8 6
3 10
...

user output
Yes

Test 2

Verdict:

input
10
4 5
3 4
2 3
9 10
...

correct output
1
10 1

user output
Yes

Test 3

Verdict:

input
10
1 8
1 3
3 5
5 7
...

correct output
3
7 10
8 2
1 9

user output
Yes

Test 4

Verdict:

input
10
1 5
3 7
2 10
3 8
...

correct output
3
10 8
6 4
5 9

user output
Yes

Test 5

Verdict:

input
10
4 8
3 4
4 6
2 3
...

correct output
3
8 7
10 9
1 6

user output
Yes

Test 6

Verdict:

input
100000
1 56967
1 56618
1 42321
1 82550
...

correct output
50000
56967 16911
56618 39942
42321 99902
82550 2538
...

user output
Yes

Test 7

Verdict:

input
100000
92297 92298
23511 23512
68057 68058
65434 65435
...

correct output
1
100000 1

user output
Yes

Test 8

Verdict:

input
100000
17747 97512
10397 12053
679 6975
4013 14565
...

correct output
25057
92881 76094
20353 87429
16069 96487
71186 52809
...

user output
Yes

Test 9

Verdict:

input
100000
72941 72942
11232 11233
73464 73465
30042 30043
...

correct output
489
16423 85168
20707 94190
36505 54940
96411 44067
...

user output
Yes

Test 10

Verdict:

input
100000
31451 31452
7473 7474
24056 24057
85181 85182
...

correct output
51
25638 2983
87594 87371
92001 50610
46744 100000
...

user output
Yes

Test 11

Verdict:

input
10
1 2
1 3
3 4
3 5
...

correct output
2
2 6
4 10

user output
Yes

Test 12

Verdict:

input
7
1 2
2 3
2 4
1 5
...

correct output
2
4 7
3 6

user output
Yes

Test 13

Verdict:

input
6
1 2
1 3
1 4
4 5
...

correct output
2
3 6
2 5

user output
Yes

Test 14

Verdict:

input
65538
1 2
1 3
1 4
3 5
...

correct output
16385
34 36
40 42
35 41
48 50
...

user output
Yes

Test 15

Verdict:

input
11
1 2
1 3
2 4
2 5
...

correct output
2
9 11
8 10

user output
Yes

Test 16

Verdict:

input
7
1 2
1 3
2 4
2 5
...

correct output
2
5 7
4 6

user output
Yes

Test 17

Verdict:

input
7
1 2
1 3
2 4
2 5
...

correct output
2
5 7
4 6

user output
Yes

Test 18

Verdict:

input
10
8 4
3 4
4 6
2 3
...

correct output
3
8 7
10 9
1 6

user output
Yes

Test 19

Verdict:

input
7
1 2
1 5
2 3
2 6
...

correct output
2
6 7
3 4

user output
Yes

Test 20

Verdict:

input
8
1 2
1 3
2 4
2 5
...

correct output
3
4 7
6 8
1 5

user output
Yes

Test 21

Verdict:

input
10
2 1
3 1
4 2
5 4
...

correct output
3
9 8
6 10
3 7

user output
Yes