Submission #1298806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298806		TadijaSebez	Flights (JOI22_flights)	C++20	15 / 100	77 ms	3908 KiB

Ali

#include "Ali.h"
#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <cassert>
using namespace std;
#define pb push_back

namespace {

const int THR=20;
const int MXG=1000;
const int B=30;

const int N=10050;
const int L=15;
int gid;
int idx[N];
string enc[N];
vector<int> nodes[N];
int sz[N];
set<pair<int,int>> bad;
vector<int> E[N];
int group[N],myIdx[N];
int par[N][L],dep[N];
}

void DFSEZ(int u,int p){
	par[u][0]=p;
	dep[u]=dep[p]+1;
	for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
	for(int v:E[u]){
		if(v!=p){
			DFSEZ(v,u);
		}
	}
}

int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=L-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
	for(int i=L-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
int DIST(int u,int v){
	return dep[u]+dep[v]-2*dep[LCA(u,v)];
}

void DFS(int u,int p){
	sz[u]=1;
	for(int v:E[u]){
		if(v==p)continue;
		if(bad.count({u,v}))continue;
		DFS(v,u);
		sz[u]+=sz[v];
	}
}

pair<int,int> Find(int u,int p,int n){
	for(int v:E[u]){
		if(v==p)continue;
		if(bad.count({u,v}))continue;
		if(sz[v]*3>=n && (n-sz[v])*3>=n){
			return {u,v};
		}
		auto tmp=Find(v,u,n);
		if(tmp.first!=-1)return tmp;
	}
	return {-1,-1};
}

void Mark(int u,int p,int g){
	group[u]=g;
	myIdx[u]=idx[g]++;
	nodes[g].pb(u);
	//printf("%i ",u);
	for(int v:E[u]){
		if(v==p)continue;
		if(bad.count({u,v}))continue;
		enc[g]+='1';
		Mark(v,u,g);
		enc[g]+='0';
	}
}

void Centroid(int u){
	DFS(u,u);
	if(sz[u]<=THR){
		//printf("Group(%i) => ",gid);
		Mark(u,u,gid);
		gid++;
		//printf("\n");
	}else{
		pair<int,int> edg=Find(u,u,sz[u]);
		//assert(edg.first!=-1);
		bad.insert(edg);
		bad.insert({edg.second,edg.first});
		Centroid(edg.first);
		Centroid(edg.second);
	}
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
	for(int i=0;i<N;i++){
		for(int j=0;j<L;j++){
			par[i][j]=0;
		}
		dep[i]=0;
		E[i].clear();
		gid=0;
		idx[i]=0;
		group[i]=0;
		myIdx[i]=0;
		nodes[i].clear();
		enc[i]="";
	}
	bad.clear();
	for(int i=0;i<N-1;i++){
		E[U[i]].pb(V[i]);
		E[V[i]].pb(U[i]);
	}
	DFSEZ(0,0);
	Centroid(0);
	for(int i=0;i<N;i++){
		SetID(i,group[i]*THR+myIdx[i]);
	}
}

std::string SendA(std::string S) {
	int val=0;
	for(int i=0;i<20;i++){
		val=val*2;
		if(S[i]=='1')val++;
	}
	int GX=val/MXG;
	int GY=val%MXG;
	int dist=0;
	int IX=0;
	int IY=0;
	if(GX!=GY){
		dist=N*2;
		int ii=0;
		for(int i:nodes[GX]){
			int jj=0;
			for(int j:nodes[GY]){
				int d=DIST(i,j);
				if(dist>d){
					dist=d;
					IX=ii;
					IY=jj;
				}
				jj++;
			}
			ii++;
		}
	}
	int num=dist*THR*THR+IX*THR+IY;
	string ans="";
	for(int i=B-1;i>=0;i--){
		if(num>>i&1)ans+="1";
		else ans+="0";
	}
	ans+=enc[GX]+"0"+enc[GY];
	//cout << ans << endl;
	return ans;
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>
#include <stack>
#include <cassert>
using namespace std;

namespace {

const int THR=20;
const int MXG=1000;
const int B=30;

int GX,GY,UX,UY,n;
vector<int> E[THR];
int par[THR],dep[THR];
}

int Rec(string T,int ptr){
	//printf("REC\n");
	for(int i=0;i<THR;i++){
		E[i].clear();
		par[i]=0;
		dep[i]=0;
	}
	stack<int> now;
	now.push(0);
	int idx=0;
	while(ptr<T.size()){
		if(T[ptr]=='1'){
			idx++;
			par[idx]=now.top();
			//printf("%i -> %i\n",par[idx],idx);
			dep[idx]=dep[now.top()]+1;
			now.push(idx);
		}else{
			now.pop();
			if(now.empty()){
				return ptr;
			}
		}
		ptr++;
	}
	return ptr;
}

int Dist(int u,int v){
	//printf("DIST %i %i\n",u,v);
	if(dep[u]<dep[v])swap(u,v);
	int ans=0;
	while(dep[u]>dep[v]){
		u=par[u];
		ans++;
	}
	while(u!=v){
		u=par[u];
		v=par[v];
		ans+=2;
	}
	return ans;
}

std::string SendB(int N, int X, int Y) {
	n=N;
	GX=X/THR;
	GY=Y/THR;
	UX=X%THR;
	UY=Y%THR;
	//printf("X: (%i, %i) Y: (%i, %i)\n",GX,UX,GY,UY);
	int val=GX*MXG+GY;
	assert(val<1000000);
	string ans="";
	for(int i=19;i>=0;i--){
		if(val>>i&1)ans+="1";
		else ans+="0";
	}
	return ans;
}

int Answer(std::string T) {
	int num=0;
	for(int i=0;i<B;i++){
		num*=2;
		if(T[i]=='1')num++;
	}
	int dist=num/THR/THR;
	int IX=(num/THR)%THR;
	int IY=num%THR;

	int ptr=Rec(T,B);
	int ans=0;
	if(GX==GY){
		ans=Dist(UX,UY);
	}else{
		ans=dist+Dist(IX,UX);
		Rec(T,ptr+1);
		ans+=Dist(IY,UY);
	}
	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85