QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#508281#5502. Dazzling MountainSorahISAWA 5079ms4068kbC++206.1kb2024-08-07 12:28:252024-08-07 12:28:25

Judging History

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

  • [2024-08-07 12:28:25]
  • 评测
  • 测评结果:WA
  • 用时:5079ms
  • 内存:4068kb
  • [2024-08-07 12:28:25]
  • 提交

answer

#ifndef NYCU_MyGO
#define NYCU_MyGO
#include NYCU_MyGO __FILE__ NYCU_MyGO

void solve() {
    int N; cin >> N;
    
    vector<vector<int>> adj(N);
    for (int i = 0; i < N-1; ++i) {
        int u, v; cin >> u >> v, --u, --v;
        adj[u].eb(v), adj[v].eb(u);
    }
    
    vector<int> sz(N, 1), dep(N, 1), par(N, 1);
    function<void(int, int)> dfs = [&](int now, int lst) {
        dep[now] = (!~lst ? 1 : dep[lst] + 1), par[now] = lst;
        for (int x : adj[now]) { if (x != lst) dfs(x, now), sz[now] += sz[x]; }
    };
    dfs(0, -1);
    
    function<bool(int, int, int)> check = [&](int val, int now, int lst) -> bool {
        if (sz[now] <= val) return (sz[now] == val);
        bool ans = true;
        for (int x : adj[now]) { if (x != lst) ans &= check(val, x, now); }
        return ans;
    };
    
    int min_dep = N, min_dep_id = -1;
    for (int i = 0; i < N; ++i) {
        if (sz[i] == 1 and chmin(min_dep, dep[i])) min_dep_id = i;
    }
    
    vector<int> ans;
    for (int i = min_dep_id; i != -1; i = par[i]) {
        if (check(sz[i], 0, -1)) ans.eb(sz[i]);
    }
    cout << SZ(ans) << "\n";
    for (int i = 0, k = SZ(ans); i < k; ++i) cout << ans[i] << " \n"[i == k-1];
}

int32_t main() {
    fastIO();
    
    int t = 1; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
#define int i64
using f80 = long double;
#define dobule f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif

/**
 *                                                                                                                 
 *                                                                                                                 
 *                                                                                                                 
 *                            iiiiii         iiiiiiiiii       iiiiiiiiiiiiii                                       
 *                       iiiiiiiiiiiii   iiiiiii    iiii    iiiiiiiiiiiiiii                          ii   iiii     
 *                    iiiiiiii     iiiiiiiii         iiii       iiii iii              iii          iiiiiiiiii      
 *                 iiiiiii          iiiiii           iiii    iiii   ii           iiiiiiiiii      iiii iiii         
 *               iiiiii            iiiii             iiii iiii        iii      iiii    iiiiiiiiiiiiiiiii  ii       
 *             iiiiii            iiiiiii            iiiiiii       iiiiiiii   iii    iiiiiiiiiiiiii iii  iiii       
 *           iiiiii             iiiiiii            iiiii   ii   iiii       iiiiiiiiiii iiii  iii iiii iiii      iii
 *          iiiii              iiiiiiii       ii        iiiii iiii    iiiiiiiii        iii iii  iii  iii  ii  iiii 
 *        iiiiii              iiiiiiii      iiiii     iiiii iiiiiiiiiiiiiiii         iii  iii  ii  iii  iii iiii   
 *       iiiii                 iiiiii     iiii     iiiiii iiiiiii    iii iii       iiii  ii   i   ii  iii  iii     
 *     iiiiii                            iiii  iiiiiiiiiiiiiii       iii iiii   iiiii  iii  ii  iii  iii  ii       
 *    iiiii                              iiiiiiii iiiiiiiiii       iiii   iiiiiiiii            ii  iii  ii         
 *   iiiii                                     iiiiii  iiii      iiiii              iii      ii   ii  i            
 * iiiiii                                  iiiiiiii   iiiii    iiiii                        ii  ii   ii            
 * iiiii                                iiii  iiii    iiiiiiiiiiii                             ii                  
 *  iii                              iiii   iiii       iiiiiiii                                                    
 *                                iiiii   iiii                                                                     
 *                              iiii     iiii                                                                      
 *                            iiii    iiiii                                                                        
 *                          iii     iiiii                                                                          
 *                        iii     iiiii                                                                            
 *                       iii   iiiiii                                                                              
 *                       iiiiiiiii                                                                                 
 *                       iiiiii                                                                                    
 *                                                                                                                 
 *                                                                                                                 
 *                                                                                                                 
**/

详细

Test #1:

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

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
Wrong Answer
time: 5079ms
memory: 4068kb

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:

63
1 3 4 34 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906
6
1 2 3 4 5 11
28
1 2 3 4 5 6 15 16 17 18 19 20 21 2...

result:

wrong answer 65th lines differ - expected: '4', found: '0'