Submission #1243259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243259		CyberCow	Beech Tree (IOI23_beechtree)	C++20	14 / 100	40 ms	9032 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);
    if(N <= 8)
    {
      for(int i = 1; i < N; i++)
      {
        v[P[i]].push_back({i, C[i]});
    }
    for (int i = 0; i < N; i++)
    {
        lc.clear();
        Dfs(i);
        int stpereb = 0;
        sort(lc.begin(), lc.end());
        do
        {
           int st = 1;
            if(lc[0] == i)
            {
                for (int j = 1; st && j < lc.size(); j++)
                {
                    if(P[lc[j]] != lc[color[C[lc[j]]]])
                    {
                       st = 0;
                        for (int j = 0; j < lc.size(); j++)
                        {
                            color[C[lc[j]]] = 0;
                           }
                        break;
                    }
                    color[C[lc[j]]]++;
                }
                if(st)
                {
                    stpereb = 1;
                }    
            }
            for (int j = 0; j < lc.size(); j++)
            {
                color[C[lc[j]]] = 0;
            }
            if(stpereb)break;
        } while (next_permutation(lc.begin(), lc.end()));
        if(stpereb)
        ans[i] = 1;
        for (int j = 0; j <= M; j++)
        {
            color[j] = 0;
        }
      }
      return ans;
   }
   int entast = 1;
   for (int i = 1; i < N; i++)
   {
      if(P[i] != i - 1)
      entast = 0;
   }
   if(entast)
   {
      int gt = 0;
      for (int i = N - 1; i > 0; i--)
      {
         if(C[i] != C[i - 1])
         {
            gt = i - 1;
            break;   
         }
      }
      for (int i = gt; i < N; i++)
      {
         ans[i] = 1;
      }
      return ans;
   }
   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: 9 / 9
• Subtask 2: 5 / 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