Submission #1178377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178377		emptypringlescan	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	151 ms	6760 KiB

incursion

#include <bits/stdc++.h>

#include "incursion.h"
using namespace std;
vector<int> adj[45005];
int n;
int sz[45005],par[45005];
bool cmp(int a, int b){
	return sz[a]>sz[b];
}
int dfs(int x, int p){
	par[x]=p;
	sz[x]=1;
	for(int i:adj[x]){
		if(i==p) continue;
		sz[x]+=dfs(i,x);
	}
	return sz[x];
}
int findcent(int x, int p){
	for(int i:adj[x]){
		if(i==p) continue;
		if(sz[i]*2>n) return findcent(i,x);
	}
	return x;
}
vector<int> mark(vector<pair<int,int> > ed, int ans){
	n=ed.size()+1;
	vector<int> ret(n,1);
	for(int i=0; i<=n; i++){
		adj[i].clear();
		par[i]=-1;
	}
	for(pair<int,int> i:ed){
		adj[i.first].push_back(i.second);
		adj[i.second].push_back(i.first);
	}
	dfs(ans,-1);
	int cent=findcent(ans,-1);
	while(cent!=-1){
		ret[cent-1]=0;
		cent=par[cent];
	}
	return ret;
}
void follow(int cur){
	sort(adj[cur].begin(),adj[cur].end(),cmp);
	for(int i:adj[cur]){
		if(i==par[cur]) continue;
		int tst=visit(i);
		if(tst) visit(cur);
		else{
			follow(i);
			return;
		}
	}
	return;
}
void locate(vector<pair<int,int> > ed, int cur, int t){
	n=ed.size()+1;
	vector<int> ret(n,1);
	for(int i=0; i<=n; i++){
		adj[i].clear();
		par[i]=-1;
	}
	for(pair<int,int> i:ed){
		adj[i.first].push_back(i.second);
		adj[i.second].push_back(i.first);
	}
	dfs(cur,-1);
	int cent=findcent(cur,-1);
	dfs(cent,-1);
	while(t==1){
		if(cur==cent){
			int legit=-1;
			for(int i:adj[cent]){
				if(sz[i]*2==n) legit=i;
			}
			assert(legit!=-1);
			cent=legit;
			dfs(cent,-1);
		}
		t=visit(par[cur]);
		cur=par[cur];
	}
	follow(cur);
}

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