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

Code

#include <bits/stdc++.h>
using namespace std;
 
#define PRINT_ARR(arr, n)                                                      \
  do {                                                                         \
    for (int i = 0; i < n; i++) {                                              \
      cout << arr[i] << " ";                                                   \
    }                                                                          \
    cout << "\n";                                                              \
  } while (0)
#define PRINT_VEC_ARR(v, n)                                                    \
  do {                                                                         \
    for (int i = 0; i < n; i++) {                                              \
      cout << i << ": ";                                                       \
      for (auto item : v[i]) {                                                 \
        cout << item.first << " " ;                                                   \
      }                                                                        \
      cout << endl;                                                            \
    }                                                                          \
  } while (0)
 
 
typedef long long ll;
typedef pair<ll, bool> pp;
 
bool dfs(int i, int c, int *color, vector<pp> *status, int n) {
  bool s = true;
  for (auto p : status[i]) {
    if (p.second) {
      if (color[p.first] != 0 && color[p.first] != c) {
        return false;
      } else if (color[p.first] == 0) {
        color[p.first] = c;
        s = dfs(p.first, c, color, status, n);
      } else {
        continue;
      }
    } else {
      if (color[p.first] == c) {
        return false;
      } else if (color[p.first] == 0){
        color[p.first] = c == 1 ? -1 : 1;
        s = dfs(p.first, (c == 1 ? -1 : 1), color, status, n);
      } else {
        continue;
      }
    }
    if (!s)
      return false;
  }
  return true;
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  int n, m;
  cin >> n >> m;
  int arr[n];
  memset(arr, 0, n * sizeof(int));
  arr[0] = 1;
  vector<pp> status[n];
 
  ll a, b, c;
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    a--;
    b--;
    status[a].push_back({b, (c == 1)});
    status[b].push_back({a, (c == 1)});
  }
 
  int color[n];
  memset(color, 0, n*sizeof(int));
  color[0] = 1;
  bool state = dfs(0, 1, color, status, n);
 
 
  cout << (state ? "Yes" : "No") << endl;
  return 0;
}

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: ACCEPTED

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

correct output
No

user output
No

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: ACCEPTED

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

correct output
No

user output
No

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:

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

correct output
No

user output
Yes

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:

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

correct output
No

user output
Yes

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:

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

correct output
No

user output
Yes

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