Submission #1265312

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

incursion

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

#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define f first
#define s second
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {int f=0;os<<'{';for(auto&i:x)os<<(f++ ? ", " : ""),os<<i;os<<"}";return os;}
void _print() {cerr << "]\n";}
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

vector<int>mark(vector<pii>f,int l){
	int n=f.size()+1;
	vector<vector<int>>adj(n);for(auto i:f)adj[i.f-1ll].push_back(i.s-1ll),adj[i.s-1ll].push_back(i.f-1ll);
	l--;
	vector<int>sz(n,1),d(n,0);
	function<void(int,int,vector<int>&)>dfs=[&](int u,int p,vector<int>&d){
		for(int i:adj[u]){
			if(i==p)continue;
			d[i]=d[u]+1; dfs(i,u,d);sz[u]+=sz[i];
		}
	};
	vector<int>centroids;
	function<void(int,int)>dfs2=[&](int u,int p){
		bool works=1;
		for(int i:adj[u]){
			if(sz[i]*2>n)works=0;
			if(i==p)continue;
			int og=sz[u],v=sz[i];
			sz[u]-=sz[i];
			sz[i]+=sz[u];
			dfs2(i,u);
			sz[u]=og;sz[i]=v;
		}
		if(works)centroids.push_back(u);
	};
	dfs(l,-1,d);
	dfs2(l,-1);
	dbg(centroids);
	assert(centroids.size()<=2);
	int cent=centroids[0];
	if(centroids.size()>1 and d[cent]>d[centroids[1]]){
		cent=centroids[1];
	}
	vector<int>d2(n,0);
	dfs(cent,-1,d2);
	vector<int>ret(n);for(int i=0;i<n;i++)ret[i]=(d[i]+d2[i]==d[cent]);
	dbg(d,d2);
	dbg(ret);
	return ret;
}

void locate(vector<pii>f,int cur,int t){
	// we can call visit
	int n=f.size()+1;
	vector<vector<int>>adj(n);for(auto i:f)adj[i.f-1ll].push_back(i.s-1ll),adj[i.s-1ll].push_back(i.f-1ll);
	vector<int>sz(n,1),d(n,0);
	function<void(int,int,vector<int>&)>dfs=[&](int u,int p,vector<int>&d){
		for(int i:adj[u]){
			if(i==p)continue;
			d[i]=d[u]+1; dfs(i,u,d);sz[u]+=sz[i];
		}
	};
	vector<int>centroids;
	function<void(int,int)>dfs2=[&](int u,int p){
		bool works=1;
		for(int i:adj[u]){
			if(sz[i]*2>n)works=0;
			if(i==p)continue;
			int og=sz[u],v=sz[i];
			sz[u]-=sz[i];
			sz[i]+=sz[u];
			dfs2(i,u);
			sz[u]=og;sz[i]=v;
		}
		if(works)centroids.push_back(u);
	};
	dfs(0,-1,d);
	dfs2(0,-1);
	dbg(centroids);
	// we have found our centroids
	// now we need to root it at the centroids (pretend they merge) and go towards them until t is satisfied
	vector<int>p(n),s(n,1);
	vector<int>checked(n),val(n);
	function<void(int,int)>dfs3=[&](int u,int par){
		p[u]=par;
		for(int i:adj[u]){
			if(i==par)continue;
			dfs3(i,u);
			s[u]+=s[i];
		}
	};
	assert(1<=centroids.size() and centroids.size()<=2);
	dfs3(centroids[0],-1);
	cur--;
	checked[cur]=1;val[cur]=t;
	while(!t){
		if(p[cur]==-1)break;
		t=visit(p[cur]+1);
		checked[p[cur]]=1;
		val[p[cur]]=t;
		cur=p[cur];
	}
	if(t==false){
		t=visit(centroids[1]+1);cur=centroids[1];
	}
	dbg(cur);
	// t is true rn so we need to descend now
	while(true){
		vector<int>kids;for(int i:adj[cur])if(i!=p[cur])kids.push_back(i);
		sort(all(kids),[&](int i,int j){return s[i]>s[j];});
		bool moved=0;
		for(int i:kids){
			if(checked[i] and val[i]){
				visit(i+1);cur=i;t=1;moved=1;break;
			}else if(checked[i])continue;
			int v=visit(i+1);
			if(v){cur=i;t=v;moved=1;break;}
			visit(cur+1);
		}
		if(!moved){
			dbg(cur);
			break;
		}
	}
	dbg("END");
}

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