Submission #1199516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199516		byunjaewoo	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	157 ms	10616 KiB

incursion

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

vector<int> mark(vector<pair<int, int>> F, int safe) {
  int n=F.size()+1;
  vector<vector<int>> adj(n);
  for(int i=0; i<n-1; i++) adj[F[i].first-1].push_back(F[i].second-1), adj[F[i].second-1].push_back(F[i].first-1);
  vector<int> siz(n, 0), par(n);
  function<void(int, int)> dfs=[&](int curr, int prev) {
    siz[curr]=1;
    for(int next:adj[curr]) if(next!=prev) par[next]=curr, dfs(next, curr), siz[curr]+=siz[next];
  };
  dfs(0, -1);
  int cent1=-1, cent2=-1;
  for(int i=0; i<n; i++) {
    bool flag=true;
    for(int next:adj[i]) if(siz[next]<siz[i] && siz[next]>n/2) flag=false;
    if(flag && n-siz[i]<=n/2) {
      if(cent1<0) cent1=i;
      else cent2=i;
    }
  }
  vector<int> ret(n, 1);
  dfs(cent1, -1), par[cent1]=-1;
  if(cent2>=0) par[cent2]=-1;
  for(int i=safe-1; i>=0; i=par[i]) ret[i]=0;
  return ret;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
  int n=F.size()+1;
  vector<vector<int>> adj(n);
  for(int i=0; i<n-1; i++) adj[F[i].first-1].push_back(F[i].second-1), adj[F[i].second-1].push_back(F[i].first-1);
  vector<int> siz(n, 0), par(n);
  function<void(int, int)> dfs=[&](int curr, int prev) {
    siz[curr]=1;
    for(int next:adj[curr]) if(next!=prev) par[next]=curr, dfs(next, curr), siz[curr]+=siz[next];
  };
  dfs(0, -1);
  int cent1=-1, cent2=-1;
  for(int i=0; i<n; i++) {
    bool flag=true;
    for(int next:adj[i]) if(siz[next]<siz[i] && siz[next]>n/2) flag=false;
    if(flag && n-siz[i]<=n/2) {
      if(cent1<0) cent1=i;
      else cent2=i;
    }
  }
  dfs(cent1, -1), par[cent1]=cent2;
  if(cent2>=0) siz[cent1]-=siz[cent2];
  vector<vector<int>> chd(n);
  for(int i=0; i<n; i++) {
    for(int j:adj[i]) if(j!=par[i]) chd[i].push_back(j);
    sort(chd[i].begin(), chd[i].end(), [&](int a, int b) {return siz[a]>siz[b];});
  }
  int prev=-1; curr--;
  while(true) {
    if(t) {
      t=visit(par[curr]+1), prev=curr, curr=par[curr];
    }
    else {
      bool flag=false;
      for(int next:chd[curr]) if(next!=prev) {
        t=visit(next+1);
        if(!t) {
          flag=true, prev=curr, curr=next;
          break;
        }
        else visit(curr+1);
      }
      if(!flag) break;
    }
  }
}

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