QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297711#7936. Eliminate TreeRifalWA 108ms44008kbC++173.6kb2024-01-05 03:02:512024-01-05 03:02:52

Judging History

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

  • [2024-01-05 03:02:52]
  • 评测
  • 测评结果:WA
  • 用时:108ms
  • 内存:44008kb
  • [2024-01-05 03:02:51]
  • 提交

answer

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 10000000000
#define INF 1000000000
#define INF2 2000000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int M = 2e5 + 5;
vector<int> v[M];
set<int> st[M];
int par[M];
bool ok[M], ok2[M];
void dfs(int s, int p) {
    par[s] = p;
    for(auto i : v[s]) {
        if(i != p) {
         dfs(i,s); }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; cin >> n;
    for(int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        st[a].insert(b);
        st[b].insert(a);
    }
    if(n == 1) {
        cout << 2 << endl; return 0;
    }
    else if(n == 2) {
        cout << 1 << endl; return 0;
    }
    dfs(1,0); deque<int> dq;
    for(int i = 1; i <= n; i++) {
        if(v[i].size() == 1) {
            ok[i] = 1;
            if(i == 1) {
                if(v[v[1][0]].size() <= 2) {
                    dq.push_front(i);
                }
                else {
                    dq.push_back(i);
                }
            }
            else {
                if(v[par[i]].size() <= 2) {
                    dq.push_front(i);
                }
                else {
                    dq.push_back(i);
                }
            }
        }
    }
    int ans = 0;
    while(!dq.empty()) {
        int x = dq.front(); dq.pop_front();
        int y = -1;
        if(ok2[x] == 1) continue;
        ok2[x] = 1;
        if(st[x].size() == 0) {
              ans += 2; continue; }
        if(st[par[x]].size() <= 0) {
        int child = *st[x].begin();
                if(st[child].size() <= 2 && st[child].size() > 0) {
                    ans++;
                }
                else {
                    ans += 2;
                }
                     for(auto i : st[x]) {
                        st[i].erase(x);
                     }
                      st[x].clear();
                     if(st[child].size() == 1) {
                        y = *st[child].begin();
                     }
                     if(st[child].size() <= 1) {
                     for(auto i : st[child]) {
                     st[i].erase(child);
                     }
                     st[child].clear();
                     ok[child] = 1;
                     ok2[child]=1;
                     }
            }
            else {
                if(st[par[x]].size() <= 2 && st[par[x]].size() > 0) {
                    ans++;
                }
                else {
                    ans += 2;
                }
                for(auto i : st[x]) {
                        st[i].erase(x);
                    }
                    st[x].clear();
                    if(st[par[x]].size() == 1) {
                        y = *st[par[x]].begin();
                    }  
                    if(st[par[x]].size() <= 1) {
                    for(auto i : st[par[x]]) {
                        st[i].erase(par[x]);
                    }
                    st[par[x]].clear();
                    ok[par[x]] = 1;
                    ok2[par[x]] = 1;
                    }
            }  
        //    cout << x << ' ' << y << endl;
            if(y != -1 && st[y].size() <= 1 && ok[y] == 0 && ok2[y] == 0) { ok[y] = 1; dq.push_front(y); }  
    }
    cout << ans << endl;
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18504kb

input:

5
1 2
2 3
3 4
3 5

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 3ms
memory: 17596kb

input:

4
1 2
2 3
3 4

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Wrong Answer
time: 108ms
memory: 44008kb

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:

162470

result:

wrong answer 1st numbers differ - expected: '138182', found: '162470'