QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#119149#5502. Dazzling Mountainhos_lyricAC ✓1380ms220916kbC++142.8kb2023-07-05 01:44:342023-07-05 01:44:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 01:44:37]
  • 评测
  • 测评结果:AC
  • 用时:1380ms
  • 内存:220916kb
  • [2023-07-05 01:44:34]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int N;
vector<int> A, B;

vector<vector<int>> graph;
vector<int> us;
vector<int> sz;
int zeit;
vector<int> dis, fin;
void dfs(int u, int p) {
  us.push_back(u);
  sz[u] = 1;
  dis[u] = zeit;
  bool leaf = true;
  for (const int v : graph[u]) if (p != v) {
    leaf = false;
    dfs(v, u);
    sz[u] += sz[v];
  }
  if (leaf) {
    ++zeit;
  }
  fin[u] = zeit;
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &N);
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    
    graph.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
      graph[A[i]].push_back(B[i]);
      graph[B[i]].push_back(A[i]);
    }
    us.clear();
    sz.assign(N, -1);
    zeit = 0;
    dis.assign(N, -1);
    fin.assign(N, -1);
    dfs(0, -1);
    
    vector<vector<int>> uss(N + 1);
    for (const int u : us) {
      uss[sz[u]].push_back(u);
    }
// cerr<<"us = "<<us<<endl;
// cerr<<"dis = "<<dis<<endl;
// cerr<<"fin = "<<fin<<endl;
// cerr<<"uss = "<<uss<<endl;
    
    vector<int> ans;
    for (int d = 1; d <= N; ++d) {
      bool ok = true;
      int now = 0;
      for (const int u : uss[d]) {
        ok = ok && (now == dis[u]);
        now = fin[u];
      }
      ok = ok && (now == zeit);
      if (ok) {
        ans.push_back(d);
      }
    }
    
    printf("%d\n", (int)ans.size());
    for (int h = 0; h < (int)ans.size(); ++h) {
      if (h) printf(" ");
      printf("%d", ans[h]);
    }
    puts("");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 579ms
memory: 4012kb

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:

ok 20000 lines

Test #3:

score: 0
Accepted
time: 1071ms
memory: 68492kb

input:

10
257056
71485 24974
175037 254578
15503 255561
2268 184070
101954 23776
151400 163190
209539 157934
61908 8578
251032 109510
106012 63219
6393 135129
229530 202665
135202 195080
36226 54716
113653 27375
130515 126621
51348 62149
190321 116509
235895 205631
193944 184367
234172 88847
217084 158554
...

output:

24809
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok 20 lines

Test #4:

score: 0
Accepted
time: 1380ms
memory: 220916kb

input:

3
1000000
929036 746780
508756 963246
215473 613289
951642 391332
605398 514190
932199 548138
439718 525533
976267 837482
522952 131368
536100 143927
866830 627096
995333 784817
209340 817981
278894 972055
340159 479037
505969 156301
962674 345998
328184 514559
522443 340810
671564 2940
233204 19714...

output:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

result:

ok 6 lines

Test #5:

score: 0
Accepted
time: 1164ms
memory: 162332kb

input:

3
1000000
762755 663578
736521 890486
762558 739995
2696 497271
66774 285301
58082 960305
515605 849755
585841 791747
805356 25220
199034 206010
792516 101430
419916 601668
256275 440770
76325 556632
286424 45286
173087 212370
760515 256873
614983 749308
248450 520646
937026 203197
698482 110785
336...

output:

97
1 999905 999906 999907 999908 999909 999910 999911 999912 999913 999914 999915 999916 999917 999918 999919 999920 999921 999922 999923 999924 999925 999926 999927 999928 999929 999930 999931 999932 999933 999934 999935 999936 999937 999938 999939 999940 999941 999942 999943 999944 999945 999946 9...

result:

ok 6 lines

Test #6:

score: 0
Accepted
time: 1067ms
memory: 117828kb

input:

4
524287
205019 282354
364309 67930
413687 214429
276475 421558
389289 353076
280299 275873
94349 273570
247189 157103
229015 223128
199377 75975
290133 428512
365384 135800
429146 366204
300847 17632
274432 256151
514401 293776
169558 105252
441686 467048
416285 490295
87525 312545
150473 67284
218...

output:

19
1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 262143 524287
2
1 524288
18
1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 65535 131071 917503
2
1 1000000

result:

ok 8 lines