Submission #1243262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243262		CyberCow	Beech Tree (IOI23_beechtree)	C++20	0 / 100	2 ms	4936 KiB

beechtree

#include <bits/stdc++.h>
using namespace std;

int color[200005];
vector<pair<int, int>> v[200005];

vector<int> lc;

void Dfs(int g)
{
    lc.push_back(g);
    for(auto to: v[g])
    {
        Dfs(to.first);
    }
}

int gag[200005];
int han[200005];
int timin[200005];
int timout[200005];
int ti = 1;

void Dfs1(int g)
{
   timin[g]= ++ti;
   for(auto to: v[g])
   {
      Dfs1(to.first);
   }
   timout[g] = ++ti;
}

bool stug(int a, int b)
{
   if(timin[a] <= timin[b] && timout[a] >= timout[b])
   {
      return 1;
   }
   return 0;
}

pair<int, int> zuyg[200005];

void Dfs2(int g)
{
   for(auto to: v[g])
   {
      Dfs2(to.first);
      han[g] += han[to.first];
   }
}


vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
   vector<int> ans(N, 0);
   Dfs1(0);
   for(int i = 1; i < N; i++)
   {
      v[P[i]].push_back({i, C[i]});
   }
   for (int i = 1; i <= M; i++)
   {
      zuyg[i] = {-1, -1};
   }
   for (int i = 1; i < N; i++)
   {
      if(zuyg[C[i]].first == -1)
      {
         zuyg[C[i]].first = P[i];
      }   
      else
         zuyg[C[i]].second = P[i];
   }
   for (int i = 1; i <= M; i++)
   {
      if(zuyg[i].first != -1)
      {
         if(zuyg[i].second != -1)
         {
            if(zuyg[i].first == zuyg[i].second)
            {
                han[zuyg[i].first]++;
            }
            else if(stug(zuyg[i].first, zuyg[i].second))
            {
               gag[zuyg[i].first]+=2;
               han[zuyg[i].first]++;
               gag[zuyg[i].second]++;
               han[zuyg[i].second]++;
            }
            else if(stug(zuyg[i].second, zuyg[i].first))
            {
               gag[zuyg[i].first]++;
               han[zuyg[i].first]++;
               gag[zuyg[i].second]+=2;
               han[zuyg[i].second]++;
            }
            else
            {
               gag[zuyg[i].first]++;
               han[zuyg[i].first]++;
               gag[zuyg[i].second]++;
               han[zuyg[i].second]++;
            }
         }
         else
         {
            gag[zuyg[i].first]++;
            han[zuyg[i].first]++;
         }
      }
   }
   Dfs2(0);
   for (int i = 0; i < N; i++)
   {
      if(gag[i] - han[i] >= 0)
      {
         ans[i] = 1;
      }
   }
   return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12