제출 #879208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879208		ezluci	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	1016 ms	49892 KiB

catinatree

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49