oj.uz

Submission #879208

# Submission time Handle Problem Language Result Execution time Memory
879208 2023-11-26T21:57:23 Z ezluci Cat in a tree (BOI17_catinatree) C++17
51 / 100
 1000 ms 49892 KB 
#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
void EZinit() {
   #ifndef EZ
   cin.tie(0)->sync_with_stdio(0);
   #else
   freopen("test.in", "r", stdin);
   freopen("test.out", "w", stdout);
   #endif
}

const int nMAX = 200e3;

int n, D;
int tat[nMAX + 1];
vector<int> fii[nMAX + 1];
vector<int> niv[nMAX + 1];
int d[nMAX + 1];

int e[2*nMAX], k;
int ermq[2*nMAX][19+1];
int est[nMAX + 1];


void dfs(int nod)
{
   e[++k] = nod;
   est[nod] = k;
   d[nod] = d[tat[nod]] + 1;
   niv[d[nod]].pb(nod);
   for (int fiu : fii[nod])
   {
      dfs(fiu);
      e[++k] = nod;
   }
}


void buildRMQ()
{
   for (int i = 1; i < 2*n; ++i)
      ermq[i][0] = e[i];
   for (int j = 1; 1<<j < 2*n; ++j)
      for (int i = 1; i + (1<<j) - 1 < 2*n; ++i)
      {
         int a = ermq[i][j-1];
         int b = ermq[i + (1<<j-1)][j-1];
         if (d[a] < d[b])
            ermq[i][j] = a;
         else
            ermq[i][j] = b;
      }
}


int LCA(int x, int y)
{
   x = est[x];
   y = est[y];
   if (x > y)
      swap(x, y);
   
   int log = __lg(y-x+1);
   int noda = ermq[x][log];
   int nodb = ermq[y - (1<<log) + 1][log];
   if (d[noda] < d[nodb]) return noda;
   return nodb;
}


int dist(int x, int y)
{
   int lca = LCA(x, y);
   return d[x] + d[y] - 2 * d[lca];
}


int main()
{
   EZinit();
   
   cin >> n >> D;
   for (int i = 2; i <= n; ++i)
   {
      cin >> tat[i];
      tat[i]++;
      fii[tat[i]].pb(i);
   }
   
   dfs(1);

   buildRMQ();
   
   vector<int> nodsUsed;
   for (int ni = n; ni >= 1; --ni)  for (int nod : niv[ni])
   {
      bool ok = 1;
      for (int oth : nodsUsed)
         if (dist(nod, oth) < D)
         {
            // cerr << nod << ' ' << oth << '\n';
            ok = 0;
            break;
         }
      
      if (ok)  nodsUsed.pb(nod);
   }

   // for (int x : nodsUsed)  cerr << x << ' ';

   cout << nodsUsed.size();
}

Compilation message

catinatree.cpp: In function 'void buildRMQ()':
catinatree.cpp:57:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   57 |          int b = ermq[i + (1<<j-1)][j-1];
      |                               ~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 3 ms 13348 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 2 ms 13148 KB Output is correct
7 Correct 2 ms 13144 KB Output is correct
8 Correct 4 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13336 KB Output is correct
11 Correct 2 ms 13148 KB Output is correct
12 Correct 2 ms 13148 KB Output is correct
13 Correct 3 ms 13340 KB Output is correct
14 Correct 3 ms 13148 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 2 ms 13148 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 2 ms 13296 KB Output is correct
19 Correct 3 ms 13148 KB Output is correct
20 Correct 2 ms 13148 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 3 ms 13348 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 2 ms 13148 KB Output is correct
7 Correct 2 ms 13144 KB Output is correct
8 Correct 4 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13336 KB Output is correct
11 Correct 2 ms 13148 KB Output is correct
12 Correct 2 ms 13148 KB Output is correct
13 Correct 3 ms 13340 KB Output is correct
14 Correct 3 ms 13148 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 2 ms 13148 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 2 ms 13296 KB Output is correct
19 Correct 3 ms 13148 KB Output is correct
20 Correct 2 ms 13148 KB Output is correct
21 Correct 3 ms 13404 KB Output is correct
22 Correct 3 ms 13372 KB Output is correct
23 Correct 3 ms 13148 KB Output is correct
24 Correct 3 ms 13148 KB Output is correct
25 Correct 6 ms 13148 KB Output is correct
26 Correct 3 ms 13148 KB Output is correct
27 Correct 4 ms 13332 KB Output is correct
28 Correct 3 ms 13404 KB Output is correct
29 Correct 5 ms 13420 KB Output is correct
30 Correct 4 ms 13404 KB Output is correct
31 Correct 3 ms 13416 KB Output is correct
32 Correct 3 ms 13148 KB Output is correct
33 Correct 4 ms 13724 KB Output is correct
34 Correct 3 ms 13148 KB Output is correct
35 Correct 3 ms 13148 KB Output is correct
36 Correct 3 ms 13404 KB Output is correct
37 Correct 3 ms 13404 KB Output is correct
38 Correct 3 ms 13416 KB Output is correct
39 Correct 4 ms 13408 KB Output is correct
40 Correct 4 ms 13404 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 3 ms 13348 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 2 ms 13148 KB Output is correct
7 Correct 2 ms 13144 KB Output is correct
8 Correct 4 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13336 KB Output is correct
11 Correct 2 ms 13148 KB Output is correct
12 Correct 2 ms 13148 KB Output is correct
13 Correct 3 ms 13340 KB Output is correct
14 Correct 3 ms 13148 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 2 ms 13148 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 2 ms 13296 KB Output is correct
19 Correct 3 ms 13148 KB Output is correct
20 Correct 2 ms 13148 KB Output is correct
21 Correct 3 ms 13404 KB Output is correct
22 Correct 3 ms 13372 KB Output is correct
23 Correct 3 ms 13148 KB Output is correct
24 Correct 3 ms 13148 KB Output is correct
25 Correct 6 ms 13148 KB Output is correct
26 Correct 3 ms 13148 KB Output is correct
27 Correct 4 ms 13332 KB Output is correct
28 Correct 3 ms 13404 KB Output is correct
29 Correct 5 ms 13420 KB Output is correct
30 Correct 4 ms 13404 KB Output is correct
31 Correct 3 ms 13416 KB Output is correct
32 Correct 3 ms 13148 KB Output is correct
33 Correct 4 ms 13724 KB Output is correct
34 Correct 3 ms 13148 KB Output is correct
35 Correct 3 ms 13148 KB Output is correct
36 Correct 3 ms 13404 KB Output is correct
37 Correct 3 ms 13404 KB Output is correct
38 Correct 3 ms 13416 KB Output is correct
39 Correct 4 ms 13408 KB Output is correct
40 Correct 4 ms 13404 KB Output is correct
41 Execution timed out 1016 ms 49892 KB Time limit exceeded
42 Halted 0 ms 0 KB -