Submission #986313

#	Time	Username	Problem	Language	Result	Execution time	Memory
986313		Pyqe	Race (IOI11_race)	C++17	100 / 100	367 ms	120144 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long d,dsu[200069],cc[200069],lz[200069][2],z,inf=1e18;
vector<pair<long long,long long>> al[200069];
bitset<200069> vtd;
multiset<pair<long long,long long>> ms[200069];
multiset<pair<long long,long long>>::iterator it,it2;

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

void jo(long long x,long long y)
{
	long long k,w;
	
	x=fd(x);
	y=fd(y);
	if(cc[x]<cc[y])
	{
		swap(x,y);
	}
	for(it=ms[y].begin();it!=ms[y].end();it++)
	{
		k=it->fr+lz[y][1];
		w=it->sc+lz[y][0];
		it2=ms[x].lower_bound({d-k-lz[x][1],-inf});
		if(it2!=ms[x].end()&&it2->fr+lz[x][1]==d-k)
		{
			z=min(z,w+it2->sc+lz[x][0]);
		}
	}
	for(it=ms[y].begin();it!=ms[y].end();it++)
	{
		k=it->fr+lz[y][1];
		w=it->sc+lz[y][0];
		ms[x].insert({k-lz[x][1],w-lz[x][0]});
	}
	dsu[y]=x;
	cc[x]+=cc[y];
}

void dfs(long long x)
{
	long long i,sz=al[x].size(),l,w;
	
	vtd[x]=1;
	dsu[x]=x;
	cc[x]=1;
	ms[x].insert({0,0});
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		w=al[x][i].sc;
		if(!vtd[l])
		{
			dfs(l);
			lz[fd(l)][0]++;
			lz[fd(l)][1]+=w;
			jo(x,l);
		}
	}
}

int best_path(int n,int od,int ed[][2],int wg[])
{
	long long i,k,l;
	
	d=od;
	for(i=0;i<n-1;i++)
	{
		k=ed[i][0];
		l=ed[i][1];
		al[k].push_back({l,wg[i]});
		al[l].push_back({k,wg[i]});
	}
	z=inf;
	dfs(0);
	if(z==inf)
	{
		z=-1;
	}
	return z;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57