Task: | Online feud |
Sender: | aalto2024g_003 |
Submission time: | 2024-10-09 17:08:15 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | ACCEPTED | 0.00 s | details |
#21 | ACCEPTED | 0.00 s | details |
#22 | ACCEPTED | 0.00 s | details |
#23 | ACCEPTED | 0.00 s | details |
#24 | ACCEPTED | 0.00 s | details |
#25 | ACCEPTED | 0.00 s | details |
#26 | ACCEPTED | 0.00 s | details |
#27 | ACCEPTED | 0.00 s | details |
#28 | ACCEPTED | 0.00 s | details |
#29 | ACCEPTED | 0.00 s | details |
#30 | ACCEPTED | 0.00 s | details |
#31 | ACCEPTED | 0.00 s | details |
#32 | ACCEPTED | 0.00 s | details |
#33 | ACCEPTED | 0.00 s | details |
#34 | ACCEPTED | 0.00 s | details |
#35 | ACCEPTED | 0.00 s | details |
#36 | ACCEPTED | 0.00 s | details |
#37 | ACCEPTED | 0.00 s | details |
#38 | ACCEPTED | 0.00 s | details |
#39 | ACCEPTED | 0.00 s | details |
#40 | ACCEPTED | 0.00 s | details |
#41 | ACCEPTED | 0.00 s | details |
#42 | ACCEPTED | 0.00 s | details |
#43 | ACCEPTED | 0.01 s | details |
#44 | ACCEPTED | 0.00 s | details |
#45 | ACCEPTED | 0.00 s | details |
#46 | ACCEPTED | 0.00 s | details |
#47 | ACCEPTED | 0.00 s | details |
#48 | ACCEPTED | 0.00 s | details |
#49 | ACCEPTED | 0.00 s | details |
#50 | ACCEPTED | 0.00 s | details |
#51 | ACCEPTED | 0.00 s | details |
#52 | ACCEPTED | 0.00 s | details |
#53 | ACCEPTED | 0.00 s | details |
#54 | ACCEPTED | 0.00 s | details |
#55 | ACCEPTED | 0.00 s | details |
#56 | ACCEPTED | 0.01 s | details |
#57 | ACCEPTED | 0.00 s | details |
#58 | ACCEPTED | 0.00 s | details |
#59 | ACCEPTED | 0.00 s | details |
#60 | ACCEPTED | 0.00 s | details |
#61 | ACCEPTED | 0.00 s | details |
#62 | ACCEPTED | 0.10 s | details |
#63 | ACCEPTED | 0.08 s | details |
#64 | ACCEPTED | 0.09 s | details |
#65 | ACCEPTED | 0.10 s | details |
#66 | ACCEPTED | 0.14 s | details |
#67 | ACCEPTED | 0.06 s | details |
#68 | ACCEPTED | 0.13 s | details |
#69 | ACCEPTED | 0.05 s | details |
#70 | ACCEPTED | 0.12 s | details |
#71 | ACCEPTED | 0.05 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:57:20: warning: statement has no effect [-Wunused-value] 57 | #define debug(...) 42 | ^~ input/code.cpp:108:5: note: in expansion of macro 'debug' 108 | debug(side); | ^~~~~
Code
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif const int N = 1e5 + 5; const int INF = 0x3f3f3f3f3f3f3f3f; signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); // RTE if input wrong datatype int n, m; cin >> n >> m; vector<vi> adj(n), gadj(n); vector<pii> good; rep(i, 0, m) { int u, v, w; cin >> u >> v >> w; u--; v--; if (w == -1) { adj[u].push_back(v); adj[v].push_back(u); } else { gadj[u].push_back(v); gadj[v].push_back(u); } } vector<int> side(n, -1); bool is_bipartite = true; queue<int> q; for (int st = 0; st < n; ++st) { if (side[st] == -1) { if (adj[st].empty()) continue; q.push(st); side[st] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int u : adj[v]) { if (side[u] == -1) { side[u] = side[v] ^ 1; q.push(u); } else { is_bipartite &= side[u] != side[v]; } } } } } debug(side); rep(i, 0, n) { if (side[i] != -1) { queue<int> qq; qq.push(i); while (sz(qq) && is_bipartite) { int u = qq.front(); qq.pop(); for (int v : gadj[u]) { if (side[v] == -1) { side[v] = side[u]; qq.push(v); } else { if (side[v] != side[u]) { is_bipartite = false; break; } } } } } } rep(i, 0, n) { if (side[i] == -1) { set<int> cur; for (int j : gadj[i]) { if (side[j] != -1) { cur.insert(side[j]); } } if (sz(cur) == 2) { is_bipartite = false; break; } } } cout << (is_bipartite ? "Yes" : "No") << endl; }
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: 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 |