QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#365340#7936. Eliminate TreeInfusedWA 109ms33508kbC++201.7kb2024-03-25 04:00:432024-03-25 04:00:44

Judging History

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

  • [2024-03-25 04:00:44]
  • 评测
  • 测评结果:WA
  • 用时:109ms
  • 内存:33508kb
  • [2024-03-25 04:00:43]
  • 提交

answer

#include "bits/stdc++.h"

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define db puts("*****")
#define sz(x) int(x.size())
#define pii pair <int , int>
#define mid(x , y) ((x+y)>>1)
#define all(x)	x.begin(),x.end()
#define y1 your_name_engraved_herein

using namespace std;

const int N = 2e5+2;
const int K = 1e3+2;
const int MOD = 998244353;

template<class T> bool umin(T& a, T b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> bool umax(T& a, T b) { if(a < b){ a = b; return 1; } return 0; }

int lvl[N], par[N], cnt;
set<int> E[N];

void dfs(int u, int p){
    par[u] = p;
    lvl[u] = lvl[p] + 1;
    for(int v : E[u]){
        if(v != p){
            dfs(v, u);
        }
    }
}

void solve(){
    int n; scanf("%d", &n);
    for(int i=0; i<n-1; i++){
        int a, b; scanf("%d%d", &a, &b);
        E[a].insert(b);
        E[b].insert(a);
    }
    dfs(1, 0);
    vector<int> v(n);
    for(int i=0; i<n; i++){
        v[i] = i+1;
    }
    sort(all(v), [&](int x, int y){
        return lvl[x] > lvl[y];
    });
    vector<bool> out(n+1, false);
    int ans = 0;
    for(int u : v){
        if(out[u]) continue;
        if(u == 1){
            ans += 2;
            out[u] = true;
        } else if(sz(E[par[u]]) <= 2) {
            ans += 1;
            out[u] = out[par[u]] = true;
            if(par[u] != 1){
                E[par[par[u]]].erase(par[u]);
            }
        } else {
            out[u] = true;
            ans += 2;
            E[par[u]].erase(u);
        }
    }
    printf("%d\n", ans);
}

int main(){
    int testcase = 1;
    // scanf("%d", &testcase);
    while(testcase--){
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14648kb

input:

5
1 2
2 3
3 4
3 5

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 13456kb

input:

4
1 2
2 3
3 4

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 109ms
memory: 33508kb

input:

196666
32025 108673
181779 17115
162570 134230
93003 39673
89144 1269
185919 154408
34896 65369
35860 44720
55698 1390
45520 189805
147867 124511
135459 132555
87303 18031
176314 59695
33352 130640
87272 39716
35749 108807
143493 94486
126512 116598
40212 70895
132216 80855
22241 188737
150354 17346...

output:

138182

result:

ok 1 number(s): "138182"

Test #4:

score: -100
Wrong Answer
time: 95ms
memory: 32880kb

input:

192941
180913 51977
128686 137679
118562 93198
60438 181978
39944 140001
169718 122100
146644 138935
22544 124591
113645 112480
128660 133392
9985 102696
4089 62155
4760 3202
116481 17579
59343 141071
81968 156270
5544 186622
117322 35780
127098 110151
148427 70933
2244 44243
3778 176132
181512 1583...

output:

135477

result:

wrong answer 1st numbers differ - expected: '135478', found: '135477'