QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #188267 | #1092. Burnished Security Updates | As3b_team_f_masr# | WA | 19ms | 55656kb | C++14 | 1.0kb | 2023-09-25 17:58:58 | 2023-09-25 17:58:58 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18;
const int N = 2e6 + 5, M = 1e4 + 5, MOD = 1e9 + 7;
#define EPS 1e-9
int n, m, a[N], vis[N], col[N], w, b, no;
vector<int> v[N];
void dfs(int node, int color) {
vis[node] = 1;
col[node] = color;
if (color) b++;
else w++;
for (auto x:v[node]) {
if (vis[x]) {
if (col[node] == col[x]) no = 1;
} else dfs(x, !color);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//memset(dp, -1, sizeof dp);
cin >> n >> m;
while (m--) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
w = b = 0;
dfs(i, 0);
ans += max(w, b);
}
}
cout << (no ? -1 : ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 50472kb
input:
4 2 1 2 3 4
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 50436kb
input:
4 4 1 2 2 3 3 4 1 4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 9ms
memory: 50732kb
input:
4 3 1 2 2 3 1 3
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 13ms
memory: 55656kb
input:
300000 49525 14 7 8 10 25 22 33 32 33 36 33 38 35 34 36 34 34 40 35 41 39 36 40 38 53 52 53 57 54 55 56 54 59 61 59 64 64 61 71 73 71 74 77 71 71 79 77 72 74 73 77 78 80 84 80 85 96 100 100 103 126 125 149 150 153 154 154 159 157 155 156 160 158 160 164 162 169 167 169 168 168 173 173 169 171 170 17...
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 14ms
memory: 55208kb
input:
299996 49689 7 10 20 19 27 26 49 44 47 48 63 57 63 58 61 59 59 62 62 60 60 64 65 74 71 66 77 76 88 84 98 99 115 118 121 115 121 116 130 126 135 141 141 139 142 143 178 174 182 180 185 189 187 193 191 190 222 227 231 235 238 239 243 240 247 240 247 246 257 254 258 256 264 266 271 267 274 268 282 279 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 19ms
memory: 55304kb
input:
299993 49815 10 12 15 18 19 21 28 31 47 52 53 52 59 55 65 62 62 66 73 72 72 76 90 85 92 85 93 85 90 92 97 94 96 100 100 99 101 103 105 104 104 107 111 105 107 112 117 115 121 117 117 124 119 121 122 120 122 123 137 133 152 151 163 161 168 169 173 172 200 201 212 215 217 215 231 224 228 229 243 241 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 13ms
memory: 55364kb
input:
299991 49386 15 12 26 19 22 23 24 22 24 23 25 27 32 36 36 34 35 38 55 54 57 54 59 62 61 60 61 64 63 62 72 71 76 74 83 78 85 81 85 82 86 87 92 86 93 95 107 110 112 108 114 115 115 119 121 115 120 116 121 120 133 131 156 160 160 164 162 161 162 163 180 178 184 186 187 184 188 186 188 189 221 220 227 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 19ms
memory: 55188kb
input:
299993 48776 5 2 3 4 9 7 11 12 14 12 26 28 35 38 47 49 60 57 57 64 62 58 65 60 65 62 76 68 81 79 80 83 80 84 83 82 83 85 89 90 99 98 104 102 111 107 111 108 112 114 120 122 140 135 150 143 144 149 157 158 159 162 164 167 169 165 172 166 171 170 190 188 195 194 195 198 209 210 230 229 239 240 261 257...
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 13ms
memory: 55208kb
input:
299997 50016 4 2 6 2 8 9 22 21 24 21 23 22 34 38 35 37 45 44 53 56 61 53 54 57 58 54 54 61 60 56 57 58 60 58 61 58 70 75 79 81 79 84 85 79 79 87 80 81 82 81 85 83 95 93 102 98 99 102 112 111 137 136 138 141 151 152 159 157 177 171 172 174 181 178 188 183 186 190 189 188 194 195 198 202 205 198 199 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 14ms
memory: 55192kb
input:
299991 49337 22 30 31 29 37 35 47 42 62 71 63 66 66 68 74 75 79 86 80 83 91 90 104 102 102 108 118 120 139 135 139 140 150 146 154 152 155 154 164 159 166 169 166 170 171 177 174 180 189 192 217 213 232 234 240 242 247 244 246 248 247 249 254 251 270 272 272 273 283 282 286 284 289 284 284 290 287 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #11:
score: -100
Wrong Answer
time: 12ms
memory: 53736kb
input:
299991 18824 7 3 13 8 12 10 36 30 34 37 46 44 48 44 73 67 106 102 104 108 139 134 135 139 145 141 144 142 175 177 189 194 190 193 210 206 214 213 253 249 253 250 283 286 302 294 309 304 311 305 345 349 381 382 393 391 391 398 408 406 417 412 427 421 463 459 517 520 531 527 542 541 559 560 574 576 60...
output:
284286
result:
wrong answer 1st numbers differ - expected: '15705', found: '284286'