Submission #1284428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284428		Faisal_Saqib	The Ties That Guide Us (CEOI23_incursion)	C++20	9 / 100	2049 ms	5008 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];
void dfs(int x,int p=-1,int h=0)
{
  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);
  }
  dfs(safe);
  vector<int> dp(n);
  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);
  }
  int par=-1;
  while(t!=0)
  {
      int pt=t,pc=curr;;
      if(ma[curr].size()==1)
      {
      curr=ma[curr][0];
      t=visit(curr);
        par=pc;
      continue;
      }
      if(ma[curr].size()==2)
      {
        if(ma[curr][0]==par)
        {
          curr=ma[curr][1]; // directly go to the other one
          t=visit(curr);
        }
        else if(ma[curr][1]==par){
          curr=ma[curr][0]; // directly go to the other one
          t=visit(curr);
        }
        else{
          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;
      }
  }
  return;
}

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