QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#620712 | #7755. Game on a Forest | 333zhan | WA | 3ms | 7160kb | C++20 | 2.8kb | 2024-10-07 20:42:24 | 2024-10-07 20:42:24 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve () {
int n, m;
cin >> n >> m;
vector <vector <int>> e (n);
for (int i = 0; i < m; i ++) {
int x, y;
cin >> x >> y;
x --; y --;
e[x].push_back (y);
e[y].push_back (x);
}
int sum = 0;
int cnt1 = 0, cnt2 = 0;
int ans = 0;
vector <int> sz (n, 1);
vector <int> ok (n);
auto dfs1 = [&] (auto &&self, int x, int fa) -> void {
ok[x] = 1;
for (auto y : e[x]) {
if (y == fa) {
continue;
}
self (self, y, x);
sz[x] += sz[y];
}
};
for (int i = 0; i < n; i ++) {
if (! ok[i]) {
dfs1 (dfs1, i, -1);
sum ++;
if (sz[i] & 1) {
cnt1 ++;
} else {
cnt2 ++;
}
}
}
auto dfs2 = [&] (auto &&self, int x, int fa, int tot) -> void {
ok[x] = 2;
int c1 = cnt1, c2 = cnt2;
if (tot - sz[x] & 1) {
c1 ++;
} else {
c2 ++;
}
for (auto y : e[x]) {
if (y == fa) {
continue;
}
if (sz[y] & 1) {
c1 ++;
} else {
c2 ++;
}
}
int now = 0;
if (c1 & 1) {
now ^= 1;
}
if (c2 & 1) {
now ^= 2;
}
if (!now) {
ans ++;
}
// cerr << x << " " << ans << '\n';
for (int y : e[x]) {
if (y == fa) {
continue;
}
c1 = cnt1;
c2 = cnt2;
if (sz[y] & 1) {
c1 ++;
} else {
c2 ++;
}
if (tot - sz[y] & 1) {
c1 ++;
} else {
c2 ++;
}
int now = 0;
if (c1 & 1) {
now ^= 1;
}
if (c2 & 1) {
now ^= 2;
}
if (!now) {
ans ++;
}
self (self, y, x, tot);
}
};
for (int i = 0; i < n; i ++) {
if (ok[i] == 1) {
if (sz[i] & 1) {
cnt1 --;
} else {
cnt2 --;
}
dfs2 (dfs2, i, -1, sz[i]);
if (sz[i] & 1) {
cnt1 ++;
} else {
cnt2 ++;
}
}
}
cout << ans << '\n';
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
int T = 1;
// cin >> T;
while (T --) {
solve ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 1 1 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 3 1 2 2 3 3 4
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 3ms
memory: 7160kb
input:
100000 1 4647 17816
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7088kb
input:
100000 2 64075 72287 63658 66936
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 6996kb
input:
100000 3 59930 72281 31689 59132 20469 33165
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 2ms
memory: 6956kb
input:
100000 10 20391 78923 27822 80617 21749 25732 12929 79693 42889 52515 59064 99869 29031 41875 4463 17813 13407 42498 19120 20957
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 7012kb
input:
99999 101 34378 94161 67696 83255 24557 25591 11476 58475 5684 38157 33843 35321 9046 24028 14293 77681 587 42098 9402 27228 6999 13980 27118 84005 3622 8353 13545 51621 16998 63647 32912 53178 15206 15815 56517 86335 5563 93770 153 278 11242 41753 75098 76792 1695 22836 25936 33352 2765 6778 19597 ...
output:
99898
result:
wrong answer 1st numbers differ - expected: '200', found: '99898'