QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#140785 | #5157. High-quality Tree | As3b_team_f_masr# | WA | 113ms | 114260kb | C++14 | 2.2kb | 2023-08-16 20:17:08 | 2023-08-16 20:17:09 |
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, MOD = 1e9 + 7;
const int N = 1e6 + 5, M = 30005;
int t, n, m, ans;
int vis[N], timer , in[N], out[N], mx[N];
pair<int,int> dp[N];
vector<int> g[N];
set<int> lvls[N];
void solve(int s,int p,int lvl){
for(auto it:g[s]){
if(it != p){
solve(it,s,lvl+1);
if(abs(dp[s].first - dp[s].second) <= 1) continue;
int mx = max(dp[s].first , dp[s].second),mn = min(dp[s].first , dp[s].second);
{
int nlvl = mx - (mx - mn -1)+1;
auto it = lvls[nlvl].lower_bound(in[s]);
while (lvls[nlvl].end() != it){
if(it != lvls[nlvl].end() && *it < out[s]){
lvls[nlvl].erase(it);
ans++;
} else
break;
it = lvls[nlvl].lower_bound(in[s]);
}
while (1){
++nlvl;
if(lvls[nlvl].size()){
ans += lvls[nlvl].size();
lvls[nlvl].clear();
}else
break;
}
}
}
}
}
int dfs(int s,int p,int lvl){
in[s] = ++timer;
lvls[lvl].insert(in[s]);
int mx = lvl;
dp[s].second = lvl;
for(auto it:g[s]){
if(it != p){
auto tmp = dfs(it,s,lvl+1);
mx = max(mx,tmp);
if(!dp[s].first) {
dp[s] = {mx , dp[s].second};
}else{
dp[s] = {dp[s].first, mx };
}
}
}
out[s] = ++timer;
return mx;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("output.txt", "w", stdout);
cin >> n;
for(int i = 1; i < n ;++i){
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,1,1);
solve(1,1,1);
cout << ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 78260kb
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: 4ms
memory: 79396kb
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: 113ms
memory: 108608kb
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: 103ms
memory: 114260kb
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: 92ms
memory: 97176kb
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: 54ms
memory: 91144kb
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: 13ms
memory: 78900kb
input:
7 1 3 3 4 1 7 7 2 7 6 3 5
output:
0
result:
ok single line: '0'
Test #8:
score: -100
Wrong Answer
time: 42ms
memory: 84596kb
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:
14846
result:
wrong answer 1st lines differ - expected: '2', found: '14846'