제출 #1284446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284446		Faisal_Saqib	The Ties That Guide Us (CEOI23_incursion)	C++20	12 / 100	161 ms	7756 KiB

incursion

#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int N=46000;
vector<int> ma[N];
int dist[N];
vector<int> path;
void dfs(int x,int p=-1,int h=0)
{
  path.push_back(x);
  dist[x]=h;
  for(auto y:ma[x])
  {
    if(y!=p)
    {
      dfs(y,x,h+1);
    }
  }
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  int n=F.size()+1;
  for(int i=0;i<=n;i++)
  {
    ma[i].clear();
  }
  for(int i=0;i<n-1;i++)
  {
    ma[F[i].first].push_back(F[i].second);
    ma[F[i].second].push_back(F[i].first);
  }
  // path 
  path.clear();
  for(int i=1;i<=n;i++)
  {
    if(ma[i].size()==1)
    {
      dfs(i);
      break;
    }
  }
  vector<int> dp(n);
  bool seens=0;
  int b=0;
  for(auto x:path)
  {
    b++;
    if(x==safe)
    {
      seens=1;
      dp[x-1]=0; // uniquely determined s
      continue;
    }
    if(seens)
    {
      if((b-1)<(n-b))
      {
        dp[x-1]=1;// go to closest leaf
      }
      else
      {
        dp[x-1]=2;// not to go coloest leaf
      }
    }
    else
    {
      if((b-1)>(n-b))
      {
        dp[x-1]=1;// go to closest leaf
      }
      else
      {
        dp[x-1]=2;// not to go coloest leaf
      }      
    }
    // (b-1) (1) (n-b)
  }
  // dfs(safe);
  // for(int i=1;i<=n;i++)dp[i-1]=dist[i];
  return dp;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
  int n=F.size()+1;
  for(int i=0;i<=n;i++)
  {
    ma[i].clear();
  }
  for(int i=0;i<n-1;i++)
  {
    ma[F[i].first].push_back(F[i].second);
    ma[F[i].second].push_back(F[i].first);
  }
    path.clear();
  for(int i=1;i<=n;i++)
  {
    if(ma[i].size()==1)
    {
      dfs(i);
      break;
    }
  }
  for(int i=0;i<n;i++)
  {
    if(path[i]==curr)
    {
      // while(t!=0)
      // {
      //   if(t==1)
      //   {
      //     if(i<(n-i-1))
      //     {
      //       visit()
      //     }
      //   }
      // }
      if(t==0)
      {
        return;
      }
      if(t==1) // go to closest
      {
        // i 1 n-i-1
        if(i<(n-i-1))
        {
          while(i>0)
          {
            t=visit(path[i-1]);
            if(t==0)
            {
              return;
            }
            i--;
          }
        }
        else{
          while(i<n-1)
          {
            t=visit(path[i+1]);
            if(t==0)return;
            i++;
          }
          return;
        }
        return;
      }
      if(t==2) // not gio clostest
      {
        if(i==(n-1-i))
        {
          // not sure case
          int pt=t;
          t=visit(path[i-1]);
          if(t==1)
          {
            // we need to go toward i-1
                i--;
          }
          else
          {
              // we need to go toward i+1
              visit(path[i]);
              t=visit(path[i+1]);
              i++;
          }
        }
         if(t==0)
      {
        return;
      }
        if(t==1) // go to closest
      {
        // i 1 n-i-1
        if(i<(n-i-1))
        {
          while(i>0)
          {
            t=visit(path[i-1]);
            if(t==0)
            {
              return;
            }
            i--;
          }
        }
        else{
          while(i<n-1)
          {
            t=visit(path[i+1]);
            if(t==0)return;
            i++;
          }
          return;
        }
        return;
      }
      else
      {
        // i 1 n-i-1
        if(i>(n-i-1))
        {
          while(i>0)
          {
            t=visit(path[i-1]);
            if(t==0)
            {
              return;
            }
            i--;
          }
        }
        else{
          while(i<n-1)
          {
            t=visit(path[i+1]);
            if(t==0)return;
            i++;
          }
          return;
        }
        return;
      }

        
      }
      return;
    }
  }
  // int par=-1;
  // while(t!=0)
  // {
  //     int pt=t,pc=curr;;
  //     int sz=ma[curr].size();
  //     for(int i=0;i<sz;i++)
  //     {
  //       if(ma[curr][i]==par)
  //         swap(ma[curr][i],ma[curr][sz-1]);
  //     }
  //     sz-=(ma[curr].back()==par); // we can ignore par
  //     if(sz==1)
  //     {
  //     curr=ma[curr][0];
  //     t=visit(curr);
  //       par=pc;
  //     continue;
  //     }
  //     if(sz==2)
  //     {
  //       curr=ma[curr][1]; // directly go to the other one
  //       t=visit(curr);
  //       if(t>pt) // moving away from safe 
  //       {
  //         visit(pc);
  //         t=visit(ma[pc][0]);
  //         curr=ma[pc][0];
  //       }
  //       par=pc;
  //     continue;
  //     }
  //     if(sz==3)
  //     {
         
  //       continue;
  //     }
  // }
  return;
}

• Subtask 0: 0 / 0
• Subtask 1: 12 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40