QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#124762 | #5157. High-quality Tree | jzh# | WA | 110ms | 50416kb | C++14 | 1.3kb | 2023-07-15 15:17:49 | 2023-07-15 15:17:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 2e5 + 5;
int dep[N];
int dp[N];
vector<int> G[N];
vector<int> H[N];
int cnt = 0;
void cal(int u) {
if (dp[u] <= 0)cnt++;
if (H[u].size() == 1) {
int to = H[u][0];
dp[to] = min({dep[to], dp[u] - 1, 1});
cal(to);
} else if (H[u].size() == 2) {
for (int i = 0; i < 2; i++) {
int r = H[u][i ^ 1];
int to = H[u][i];
dp[to] = min({dep[to], dep[r] + 1, dp[u] - 1});
cal(to);
}
}
}
int dfs(int u, int fa) {
int ans = 0;
int ans2 = 1e9;
for (int to: G[u]) {
if (to == fa)continue;
H[u].push_back(to);
int ret = dfs(to, u);
ans = max(ans, ret);
ans2 = min(ans2, ret);
dep[u] = max(dep[u], dep[to]);
}
dep[u]++;
if (H[u].size() == 1) {
return dp[u] = 2;
} else if (H[u].size() == 0) {
return dp[u] = 1;
} else if (H[u].size() == 2) {
return dp[u] = min(ans, ans2 + 1) + 1 ;
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
int ans = dfs(1, 0);
cal(1);
cout << cnt << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 12724kb
input:
6 1 2 1 3 3 4 3 5 5 6
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 13344kb
input:
12 1 2 2 3 3 4 3 5 1 6 6 7 7 8 7 9 9 10 6 11 11 12
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 103ms
memory: 37940kb
input:
200000 167246 158246 40931 40296 178588 27974 35171 899 4204 163250 101422 9230 55420 93371 16012 140142 28866 154497 33519 180725 50361 52348 46923 175364 126599 169575 15138 34958 164256 64770 63123 130169 154172 168301 127476 54744 199964 81879 173765 69220 178225 73653 59861 46415 138112 17507 8...
output:
199998
result:
ok single line: '199998'
Test #4:
score: 0
Accepted
time: 110ms
memory: 50416kb
input:
200000 144434 24107 75087 108465 38670 156657 31235 30143 40544 44213 51188 21788 170574 164351 14169 155909 120876 119956 196361 140453 197958 142813 23944 62568 12098 71652 162226 122184 123783 86178 70076 115586 74439 94246 83296 36713 182500 16937 174946 154091 97484 194764 179943 61793 114439 1...
output:
199998
result:
ok single line: '199998'
Test #5:
score: 0
Accepted
time: 56ms
memory: 25104kb
input:
200000 42469 8516 3910 143673 129125 150433 170053 160404 147325 66173 130784 195620 183508 43943 90940 88012 187183 803 139576 36677 190280 71191 107959 177664 14308 20402 93449 130555 80315 75413 178265 104526 4428 8875 151397 91172 181321 47276 105060 81973 196326 19584 44364 56143 187070 195424 ...
output:
199998
result:
ok single line: '199998'
Test #6:
score: 0
Accepted
time: 48ms
memory: 20228kb
input:
131071 94531 87688 119005 53065 70725 126770 61026 82294 114384 270 98205 38915 61461 14652 123122 36872 37639 52311 17774 89648 79899 59785 6033 52465 15449 93250 43849 18174 2665 82543 26740 15199 71645 14339 45549 119270 22896 70677 126250 23614 5796 85715 92715 25280 119740 8911 17923 5547 47703...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 13820kb
input:
7 1 3 3 4 1 7 7 2 7 6 3 5
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 14ms
memory: 17104kb
input:
75026 12155 64806 40053 74785 70103 1220 72989 33966 74199 66365 52024 24358 54545 52118 52572 28566 68873 41146 10161 67848 41221 63589 72291 44013 51515 14784 12150 33009 3919 23413 61773 13741 21172 17759 27774 65766 58702 13619 11690 19263 45469 30662 33296 45184 51641 13235 11413 52734 74437 57...
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 6ms
memory: 14624kb
input:
10947 7184 5103 1433 10766 3794 8428 1438 8926 2493 7796 6753 7135 3304 4497 9148 8680 4013 2259 3067 8641 2809 9523 9557 2452 8392 3411 1121 6418 5150 133 8893 3701 7864 3044 7152 705 3856 5325 10943 4760 9792 7866 6959 6282 1120 7627 2952 9675 10407 9119 2489 1131 907 4948 4175 3572 4178 337 226 7...
output:
2
result:
ok single line: '2'
Test #10:
score: -100
Wrong Answer
time: 3ms
memory: 13244kb
input:
8375 5605 5852 7762 3219 1669 4378 341 6410 1502 1920 706 8356 5088 5723 1326 6305 2433 5341 5185 948 7639 5745 6173 7572 4736 7204 8081 3452 2414 6798 156 7332 6627 2209 876 5078 2666 292 5041 7782 7118 807 6897 5220 5865 1273 6546 1506 4306 7980 1119 6488 4795 5942 6219 7729 8119 1572 4027 4817 46...
output:
700
result:
wrong answer 1st lines differ - expected: '701', found: '700'