QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140785#5157. High-quality TreeAs3b_team_f_masr#WA 113ms114260kbC++142.2kb2023-08-16 20:17:082023-08-16 20:17:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-16 20:17:09]
  • 评测
  • 测评结果:WA
  • 用时:113ms
  • 内存:114260kb
  • [2023-08-16 20:17:08]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'