QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225089#5502. Dazzling MountainsgrcnTL 326ms97260kbC++171.3kb2023-10-23 22:54:502023-10-23 22:54:51

Judging History

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

  • [2023-10-23 22:54:51]
  • 评测
  • 测评结果:TL
  • 用时:326ms
  • 内存:97260kb
  • [2023-10-23 22:54:50]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

int n;
vector<vector<int>> G;
vector<int> P, C;

int dfs(int v, int p) {
    int c = 1;
    for(const auto& u : G[v]) {
        if(u==p) continue;
        c += dfs(u, v);
    }
    P[v] = p;
    C[v] = c;
    return c;
}

set<int> D;

void get_path(int v) {
    if(v==-1) return;
    D.emplace(C[v]);
    get_path(P[v]);
}

void solve() {
    dfs(0, -1);
    set<int> ans;
    for(int i = 1 ; i <= 1e6 ; ++i) ans.emplace(i);

    for(int v = 1 ; v < n ; ++v) {
        if(G[v].size() == 1) {
            D.clear();
            get_path(v);
            set<int> buf = ans;
            for(const auto& c : buf) {
                if(!D.count(c)) ans.erase(c);
            }
        }
    }

    cout << ans.size() << '\n';
    for(const auto& c : ans) cout << c << ' ';
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie( nullptr);

    int t, a, b;
    cin >> t;
    while(t--) {
        cin >> n;
        G = vector<vector<int>>(n);
        P = C = vector<int>(n);
        for(int i = 1; i < n ; ++i) {
            cin >> a >> b;
            G[a-1].emplace_back(b-1);
            G[b-1].emplace_back(a-1);
        }
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 326ms
memory: 97260kb

input:

1
9
1 2
2 3
3 4
3 5
2 6
6 7
7 8
7 9

output:

4
1 3 8 9 

result:

ok 2 lines

Test #2:

score: -100
Time Limit Exceeded

input:

10000
906
675 189
555 889
491 97
791 419
175 694
713 842
788 513
159 354
670 815
652 546
253 87
89 278
563 429
522 900
202 657
331 865
35 605
735 532
612 471
657 386
7 886
856 164
224 777
73 534
481 631
711 698
240 465
115 181
191 825
311 155
709 501
207 849
294 546
591 682
96 405
210 696
861 13
781...

output:


result: