QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#529761#8134. LCA CountingPhangWA 2ms9072kbC++141.0kb2024-08-24 13:56:062024-08-24 13:56:06

Judging History

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

  • [2024-08-24 13:56:06]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9072kb
  • [2024-08-24 13:56:06]
  • 提交

answer

#include<bits/stdc++.h>
#define rep1(i, a, b) for(int i = a; i <= b; ++i)
#define rep2(i, a, b) for(int i = a; i >= b; --i)
#define ll long long
#define ft first
#define sd second
#define pb push_back
#define pii pair <int, int> 
#define ptc putchar
#define ld long double
#define debug puts("-------------------")
const int N = 2e5 + 10;
using namespace std;
int n, f[N], num1, num2, cnt;
vector <int> e[N];
void dfs(int u) {
   int num = 0;
   for(auto v : e[u]) {
      dfs(v); num += f[v]; f[u] |= f[v];
   } int x = e[u].size();
   if(x > 1) {
      ++num1; f[u] = 1;
      if(num > 2) {
         num1 -= num - 2;
         num2 += num - 2;
      }
   }
   if(u > 1 && !x) ++cnt;
}
int main() {
   cin >> n;
   rep1(i, 2, n) {
      int x; cin >> x;
      e[x].pb(i);
   } dfs(1);
   int nw = 1, flg = 0;
   // cout << cnt << '\n';
   rep1(i, 1, cnt) {
      cout << nw << ' '; ++nw;
      if(num1) ++nw, --num1;
      else if(flg && num2) ++nw, --num2, flg = 0;
      else if(!flg) flg = 1;
   }
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8412kb

input:

7
1 1 2 4 2 2

output:

1 3 5 6 

result:

ok 4 number(s): "1 3 5 6"

Test #2:

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

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 5 6 7 8 9 

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 8324kb

input:

10
1 2 2 4 5 6 1 2 4

output:

1 3 5 7 8 

result:

ok 5 number(s): "1 3 5 7 8"

Test #4:

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

input:

10
1 2 3 3 3 5 6 4 9

output:

1 3 4 

result:

ok 3 number(s): "1 3 4"

Test #5:

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

input:

1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...

output:

1 3 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 12...

result:

ok 962 numbers

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 8388kb

input:

1000
1 1 1 1 1 1 1 2 2 1 2 3 1 1 1 2 2 1 1 1 2 1 2 3 8 2 2 2 8 1 6 3 1 1 1 4 2 14 8 2 1 1 1 3 1 4 1 1 3 11 1 1 2 2 3 2 5 5 6 5 3 3 10 5 3 1 9 14 3 19 4 15 4 3 3 10 3 10 5 1 2 12 7 13 3 9 6 19 9 6 4 3 5 28 10 16 8 12 39 1 11 12 2 2 10 15 5 28 10 4 4 5 5 18 15 15 11 5 25 7 2 10 1 24 8 15 14 11 38 9 9 ...

output:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 82 84 85 87 88 90 91 93 94 96 97 99 100 102 103 105 106 108 109 111 112 114 115 117 118 120 121 123 124 126 127 129 130 132 133 135 136 138 139 141 142 144 145 147 148 150 151 153 15...

result:

wrong answer 15th numbers differ - expected: '28', found: '29'