CSES - Aalto Competitive Programming 2024 - wk6 - Wed - Results
Submission details
Task:Online feud
Sender:aalto2024g_002
Submission time:2024-10-09 16:55:00 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#90.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#120.01 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#18ACCEPTED0.01 sdetails
#19ACCEPTED0.01 sdetails
#20ACCEPTED0.01 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.01 sdetails
#23ACCEPTED0.01 sdetails
#24ACCEPTED0.01 sdetails
#25ACCEPTED0.01 sdetails
#26ACCEPTED0.01 sdetails
#27ACCEPTED0.01 sdetails
#28ACCEPTED0.01 sdetails
#29ACCEPTED0.01 sdetails
#30ACCEPTED0.01 sdetails
#31ACCEPTED0.01 sdetails
#32ACCEPTED0.01 sdetails
#33ACCEPTED0.01 sdetails
#34ACCEPTED0.01 sdetails
#35ACCEPTED0.01 sdetails
#36ACCEPTED0.01 sdetails
#37ACCEPTED0.01 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.01 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.01 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.01 sdetails
#49ACCEPTED0.01 sdetails
#50ACCEPTED0.01 sdetails
#51ACCEPTED0.01 sdetails
#52ACCEPTED0.01 sdetails
#53ACCEPTED0.01 sdetails
#54ACCEPTED0.01 sdetails
#55ACCEPTED0.01 sdetails
#56ACCEPTED0.01 sdetails
#57ACCEPTED0.01 sdetails
#58ACCEPTED0.01 sdetails
#59ACCEPTED0.01 sdetails
#60ACCEPTED0.01 sdetails
#61ACCEPTED0.01 sdetails
#62ACCEPTED0.17 sdetails
#63ACCEPTED0.15 sdetails
#64ACCEPTED0.16 sdetails
#65ACCEPTED0.20 sdetails
#66ACCEPTED0.24 sdetails
#67ACCEPTED0.13 sdetails
#68ACCEPTED0.23 sdetails
#69ACCEPTED0.11 sdetails
#70ACCEPTED0.23 sdetails
#71ACCEPTED0.10 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5;
vector<int> V[N];
vector<int> D[N];
int Z[N];

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    if (c == -1) {
      D[a-1].push_back(b-1);
      D[b-1].push_back(a-1);
    } else {
      V[a-1].push_back(b-1);
      V[b-1].push_back(a-1);
    }
  }
  unordered_set<int> S;
  for (int i = 1; i < n; ++i) {
    S.insert(i);
  }
  queue<pair<int,int>> Q;
  Q.push({0,1});
  Z[0] = 1;
  while (!S.empty()) {
    if (Q.empty()) {
      int i = *S.begin();
      Q.push({i,1});
      Z[i] = 1;
      S.erase(S.begin());
    }
    auto [i,s] = Q.front(); Q.pop();
    for (int j : V[i]) {
      if (!Z[j]) {
        Z[j] = s;
        Q.push({j,s});
        S.erase(S.find(j));
      } else if (Z[j] != s) {
        cout << "No\n";
        return 0;
      }
    }
    for (int j : D[i]) {
      if (!Z[j]) {
        Z[j] = -s;
        Q.push({j,-s});
        S.erase(S.find(j));
      } else if (Z[j] == s) {
        cout << "No\n";
        return 0;
      }
    }
  }
  cout << "Yes\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
2 4
2 1 1
1 2 -1
1 2 1
1 2 -1

correct output
No

user output
No

Test 2

Verdict: ACCEPTED

input
2 4
1 2 -1
2 1 -1
1 2 -1
1 2 -1

correct output
Yes

user output
Yes

Test 3

Verdict: ACCEPTED

input
3 2
2 3 1
3 2 1

correct output
Yes

user output
Yes

Test 4

Verdict: ACCEPTED

input
3 4
3 1 -1
2 1 -1
2 1 -1
1 2 -1

correct output
Yes

user output
Yes

Test 5

Verdict: ACCEPTED

input
3 5
1 2 1
3 2 -1
3 2 1
3 2 1
...

correct output
No

user output
No

Test 6

Verdict: ACCEPTED

input
4 3
4 1 -1
1 2 1
2 4 -1

correct output
Yes

user output
Yes

Test 7

Verdict: ACCEPTED

input
4 8
3 4 1
1 3 -1
2 3 -1
1 2 1
...

correct output
Yes

user output
Yes

Test 8

Verdict: ACCEPTED

input
4 8
3 2 -1
3 1 -1
1 2 1
1 2 1
...

correct output
Yes

user output
Yes

Test 9

Verdict:

input
4 7
3 4 1
3 2 -1
2 1 1
1 4 -1
...

correct output
No

user output
Yes

Test 10

Verdict: ACCEPTED

input
4 8
3 1 -1
1 2 1
4 3 1
1 2 -1
...

correct output
No

user output
No

Test 11

Verdict: ACCEPTED

input
4 7
1 3 -1
4 2 1
3 4 1
4 2 -1
...

correct output
No

user output
No

Test 12

Verdict:

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

correct output
No

user output
Yes

Test 13

Verdict: ACCEPTED

input
5 6
4 5 1
1 2 -1
1 2 1
2 1 1
...

correct output
No

user output
No

Test 14

Verdict: ACCEPTED

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

correct output
Yes

user output
Yes

Test 15

Verdict: ACCEPTED

input
5 7
4 5 1
1 3 1
1 4 -1
1 4 -1
...

correct output
Yes

user output
Yes

Test 16

Verdict: ACCEPTED

input
5 10
3 1 -1
5 4 -1
4 3 1
1 5 1
...

correct output
No

user output
No

Test 17

Verdict: ACCEPTED

input
5 4
4 5 -1
5 3 -1
3 5 -1
3 4 1

correct output
Yes

user output
Yes

Test 18

Verdict: ACCEPTED

input
5 10
1 5 -1
1 3 -1
3 4 -1
3 4 -1
...

correct output
Yes

user output
Yes

Test 19

Verdict: ACCEPTED

input
5 3
5 2 -1
4 3 -1
2 4 -1

correct output
Yes

user output
Yes

Test 20

Verdict: ACCEPTED

input
5 9
5 4 -1
1 5 -1
3 5 -1
1 3 1
...

correct output
Yes

user output
Yes

Test 21

Verdict: ACCEPTED

input
5 3
1 3 -1
1 3 -1
3 4 1

correct output
Yes

user output
Yes

Test 22

Verdict: ACCEPTED

input
10 14
8 9 -1
9 6 -1
5 7 -1
4 5 1
...

correct output
No

user output
No

Test 23

Verdict: ACCEPTED

input
10 12
8 10 1
2 4 -1
2 3 1
4 2 1
...

correct output
No

user output
No

Test 24

Verdict: ACCEPTED

input
10 12
9 10 1
2 5 1
8 10 1
5 8 1
...

correct output
Yes

user output
Yes

Test 25

Verdict: ACCEPTED

input
10 14
8 10 1
3 7 1
1 8 -1
1 8 -1
...

correct output
Yes

user output
Yes

Test 26

Verdict: ACCEPTED

input
10 20
6 2 -1
9 8 -1
7 6 1
2 10 1
...

correct output
No

user output
No

Test 27

Verdict: ACCEPTED

input
10 9
9 10 1
9 10 1
9 7 -1
3 10 -1
...

correct output
Yes

user output
Yes

Test 28

Verdict: ACCEPTED

input
10 19
4 3 -1
2 10 -1
1 6 -1
5 6 1
...

correct output
No

user output
No

Test 29

Verdict: ACCEPTED

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

correct output
Yes

user output
Yes

Test 30

Verdict: ACCEPTED

input
10 19
10 8 -1
1 10 -1
5 10 -1
2 6 1
...

correct output
Yes

user output
Yes

Test 31

Verdict: ACCEPTED

input
10 6
3 6 -1
1 6 -1
6 7 1
1 7 -1
...

correct output
Yes

user output
Yes

Test 32

Verdict: ACCEPTED

input
100 133
72 85 -1
86 55 -1
43 63 -1
39 44 1
...

correct output
No

user output
No

Test 33

Verdict: ACCEPTED

input
100 113
73 94 1
13 31 -1
15 24 1
40 19 1
...

correct output
No

user output
No

Test 34

Verdict: ACCEPTED

input
100 116
1 2 1
1 34 -1
71 1 -1
1 50 -1
...

correct output
Yes

user output
Yes

Test 35

Verdict: ACCEPTED

input
100 133
74 88 1
31 66 1
9 72 -1
4 73 -1
...

correct output
Yes

user output
Yes

Test 36

Verdict: ACCEPTED

input
100 196
55 18 -1
86 72 -1
70 60 1
15 98 1
...

correct output
No

user output
No

Test 37

Verdict: ACCEPTED

input
100 84
92 100 1
89 96 1
92 67 -1
26 100 -1
...

correct output
Yes

user output
Yes

Test 38

Verdict: ACCEPTED

input
100 184
34 21 -1
7 5 1
11 99 -1
10 53 -1
...

correct output
No

user output
No

Test 39

Verdict: ACCEPTED

input
100 62
100 34 -1
85 76 -1
39 79 -1
21 78 -1
...

correct output
Yes

user output
Yes

Test 40

Verdict: ACCEPTED

input
100 182
98 84 -1
98 99 1
99 100 1
51 100 -1
...

correct output
Yes

user output
Yes

Test 41

Verdict: ACCEPTED

input
100 52
25 51 -1
8 51 -1
57 68 1
5 70 -1
...

correct output
Yes

user output
Yes

Test 42

Verdict: ACCEPTED

input
200 265
144 169 -1
172 109 -1
85 125 -1
77 88 1
...

correct output
No

user output
No

Test 43

Verdict: ACCEPTED

input
200 226
145 187 1
26 61 -1
30 48 1
80 38 1
...

correct output
No

user output
No

Test 44

Verdict: ACCEPTED

input
200 231
4 5 1
3 68 -1
142 2 -1
2 100 -1
...

correct output
Yes

user output
Yes

Test 45

Verdict: ACCEPTED

input
200 266
149 176 1
62 133 1
18 144 -1
8 147 -1
...

correct output
Yes

user output
Yes

Test 46

Verdict: ACCEPTED

input
200 391
110 35 -1
172 143 -1
140 120 1
29 196 1
...

correct output
No

user output
No

Test 47

Verdict: ACCEPTED

input
200 167
184 199 1
177 192 1
184 134 -1
52 200 -1
...

correct output
Yes

user output
Yes

Test 48

Verdict: ACCEPTED

input
200 368
67 42 -1
13 9 1
22 198 -1
20 106 -1
...

correct output
No

user output
No

Test 49

Verdict: ACCEPTED

input
200 123
200 68 -1
169 152 -1
78 159 -1
42 156 -1
...

correct output
Yes

user output
Yes

Test 50

Verdict: ACCEPTED

input
200 363
196 168 -1
196 197 1
198 199 1
101 200 -1
...

correct output
Yes

user output
Yes

Test 51

Verdict: ACCEPTED

input
200 104
50 101 -1
15 102 -1
114 136 1
9 140 -1
...

correct output
Yes

user output
Yes

Test 52

Verdict: ACCEPTED

input
1000 1324
716 845 -1
858 545 -1
424 624 -1
385 438 1
...

correct output
No

user output
No

Test 53

Verdict: ACCEPTED

input
1000 1126
721 933 1
129 303 -1
147 237 1
397 187 1
...

correct output
No

user output
No

Test 54

Verdict: ACCEPTED

input
1000 1154
23 24 1
11 338 -1
707 6 -1
8 499 -1
...

correct output
Yes

user output
Yes

Test 55

Verdict: ACCEPTED

input
1000 1327
744 875 1
310 667 1
89 720 -1
37 736 -1
...

correct output
Yes

user output
Yes

Test 56

Verdict: ACCEPTED

input
1000 1951
548 173 -1
856 715 -1
698 598 1
142 977 1
...

correct output
No

user output
No

Test 57

Verdict: ACCEPTED

input
1000 833
917 994 1
882 955 1
917 667 -1
259 999 -1
...

correct output
Yes

user output
Yes

Test 58

Verdict: ACCEPTED

input
1000 1840
332 210 -1
65 42 1
108 986 -1
100 530 -1
...

correct output
No

user output
No

Test 59

Verdict: ACCEPTED

input
1000 615
996 342 -1
848 762 -1
391 799 -1
210 783 -1
...

correct output
Yes

user output
Yes

Test 60

Verdict: ACCEPTED

input
1000 1811
981 842 -1
982 983 1
992 996 1
506 996 -1
...

correct output
Yes

user output
Yes

Test 61

Verdict: ACCEPTED

input
1000 516
249 505 -1
72 508 -1
570 677 1
43 699 -1
...

correct output
Yes

user output
Yes

Test 62

Verdict: ACCEPTED

input
100000 132323
71521 84428 -1
85796 54490 -1
42367 62358 -1
38439 43760 1
...

correct output
No

user output
No

Test 63

Verdict: ACCEPTED

input
100000 112554
72034 93258 1
12813 30234 -1
14676 23610 1
39659 18627 1
...

correct output
No

user output
No

Test 64

Verdict: ACCEPTED

input
100000 115400
2456 2516 1
1090 33816 -1
70668 531 -1
777 49853 -1
...

correct output
Yes

user output
Yes

Test 65

Verdict: ACCEPTED

input
100000 132621
74356 87456 1
30951 66681 1
8894 72001 -1
3645 73546 -1
...

correct output
Yes

user output
Yes

Test 66

Verdict: ACCEPTED

input
100000 195056
54725 17270 -1
85564 71483 -1
69774 59757 1
14147 97629 1
...

correct output
No

user output
No

Test 67

Verdict: ACCEPTED

input
100000 83300
91776 99331 1
88235 95433 1
91652 66692 -1
25844 99882 -1
...

correct output
Yes

user output
Yes

Test 68

Verdict: ACCEPTED

input
100000 183930
33199 20941 -1
6426 4170 1
10766 98505 -1
9948 52983 -1
...

correct output
No

user output
No

Test 69

Verdict: ACCEPTED

input
100000 61447
99521 34194 -1
84772 76278 -1
39085 79902 -1
20937 78344 -1
...

correct output
Yes

user output
Yes

Test 70

Verdict: ACCEPTED

input
100000 181015
98043 84187 -1
98183 98204 1
99264 99561 1
50624 99598 -1
...

correct output
Yes

user output
Yes

Test 71

Verdict: ACCEPTED

input
100000 51557
24883 50564 -1
7133 50852 -1
57039 67698 1
4219 69908 -1
...

correct output
Yes

user output
Yes