Submission #1166384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166384		Mighilon	The Ties That Guide Us (CEOI23_incursion)	C++20	0 / 100	98 ms	6644 KiB

incursion

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

typedef vector<int> vi;

#define f first
#define s second

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  safe--;
  int n=F.size()+1;
  vector<vi> adj(n);
  for(auto i: F){
    i.f--;i.s--;
    adj[i.f].push_back(i.s);
    adj[i.s].push_back(i.f);
  }
  vi sz(n);
  function<int(int,int)> get_size=[&](int v, int p)->int{
    sz[v]=1;
    for(auto u: adj[v]){
      if(u==p)continue;
      sz[v]+=get_size(u,v);
    }
    return sz[v];
  };
  get_size(0,-1);
  function<int(int,int,int)> find_ce=[&](int v, int p,int s)->int{
    for(auto u: adj[v]){
      if(u==p)continue;
      if(sz[u]>=s)
        return find_ce(u,v,s);
    }
    return v;
  };
  int ce=find_ce(0,-1,n/2);
  vi marked(n);
  function<int(int, int)> mark_nodes=[&](int v, int p)->int{
    if(v==safe){
      marked[v]=1;
      return 1;
    }
    for(auto u: adj[v]){
      if(u==p)continue;
      marked[v]|=mark_nodes(u,v);
    }
    return marked[v];
  };
  mark_nodes(ce,-1);

  get_size(ce,-1);
  int ce2=find_ce(ce,-1,(n+1)/2);
  // cout<<ce<< " "<<ce2<<endl;
  if(ce!=ce2){
    if(marked[ce2])
      marked[ce]=0;
  }
  else{
    marked[ce]=0;
  }
  return marked;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
  curr--;
  int n=F.size()+1;
  vector<vi> adj(n);
  for(auto i: F){
    i.f--;i.s--;
    adj[i.f].push_back(i.s);
    adj[i.s].push_back(i.f);
  }
  vi sz(n),pa(n);
  function<int(int,int)> get_size=[&](int v, int p)->int{
    // cout<<"{"<<v+1<<","<<p+1<<"}"<<endl;
    sz[v]=1;
    for(auto u: adj[v]){
      if(u==p)continue;
      pa[u]=v;
      sz[v]+=get_size(u,v);
    }
    return sz[v];
  };
  get_size(0,-1);
  function<int(int,int,int)> find_ce=[&](int v, int p,int s)->int{
    for(auto u: adj[v]){
      if(u==p)continue;
      if(sz[u]>s)
        return find_ce(u,v,s);
    }
    return v;
  };
  int ce=find_ce(0,-1,n/2);
  get_size(ce,-1);
  // for(auto i: pa)cout<<i+1<<" ";
  // cout<<endl;
  for(auto u: adj[ce]){
    if(sz[u]>=n/2){
      pa[ce]=u;
    }
  }
  vi used(n);
  // cerr<<"--"<<ce+1<<endl;
  // for(auto i: pa)cout<<i+1<<" ";
  // cout<<endl;
  // int x=100;
  // while(x--){
  while(true){
    used[curr]=1;
    if(t==0){
      t=visit(pa[curr]+1);
      curr=pa[curr];
    }
    else{
      vi tmp;
      for(auto u: adj[curr]){
        if(u==pa[curr]||used[u])continue;
        tmp.push_back(u);
      }
      if(tmp.empty()){
        return;
      }
      sort(tmp.begin(),tmp.end(), [&](int a, int b){return sz[a]>sz[b];});
      t=visit(tmp[0]+1);
      curr=tmp[0];
    }
  }
}

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