Submission #1210464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210464		mychecksedad	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	164 ms	16920 KiB

incursion

/* Author : Mychecksdead  */
#include "incursion.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define cerr if(false) cerr
const int N = 50000;

vi g[N], put;
int s[N], n;
void dfs(int v, int p){
  s[v] = 1;
  int mx = -1;
  for(int u: g[v]){
    if(u != p){
      dfs(u, v);
      s[v] += s[u];
      mx = max(mx, s[u]);
    }
  }
  int parsz = n - s[v];
  cerr << parsz << ' ' << mx <<'\n';
  if(parsz >= mx){
    put[v] = 0;
  }else{
    put[v] = 1;
  }
}


std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  n = F.size() + 1;
  --safe;
  for(int i = 0; i + 1 < n; ++i){
    g[F[i].ff - 1].pb(F[i].ss - 1);
    g[F[i].ss - 1].pb(F[i].ff - 1);
  }
  put.resize(n);
  dfs(safe, safe);
  return put;
}

vi G[N], go[N][2];
int S[N], m;
void dfs2(int v, int p){
  S[v] = 1;
  vector<pii> U;
  for(int u: G[v]){
    if(u != p){
      dfs2(u, v);
      S[v] += S[u];
      U.pb({S[u], u});
    }
  }
  if(v != p) U.pb({m - S[v], p});
  sort(all(U), greater<pii>());
  go[v][0].pb(U[0].ss);
  for(int i = 1; i < U.size(); ++i){
    if(U[i].ff == U[0].ff) go[v][0].pb(U[i].ss);
    else go[v][1].pb(U[i].ss);
  }
//   cerr << v << '\n';
// for(int x: go[v][0]) cerr << x << ' '; cerr << '\n';
// for(int x: go[v][1]) cerr << x << ' '; cerr << '\n';
//   cerr << '\n';
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
  m = F.size() + 1;
  vector<array<int, 2>> cnt(m + 2);
  for(int i = 0; i + 1 < m; ++i){
    G[F[i].ff].pb(F[i].ss);
    G[F[i].ss].pb(F[i].ff);
  }
  int root = 1;
  for(int i = 1; i <= m; ++i){
    if(G[i].size() == 1) root = i; 
  }
  dfs2(root, root);

  int v = curr;
  while(true){
    cnt[v][t]++;
    if(cnt[v][1] >= 3 && t == 1){
      return;
    }
    if(t == 1 && go[v][1].size() == 0) return;
    int nxt;
    if(t == 0){
      nxt = go[v][0][(cnt[v][0] - 1) % (int) go[v][0].size()];
    }else{
      nxt = go[v][1][(cnt[v][1] - 1) % (int) go[v][1].size()];
    }
    t = visit(nxt);
    v = nxt;
  }


  return;
}

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