Submission #877820

#	Time	Username	Problem	Language	Result	Execution time	Memory
877820		mahmoudbadawy	Race (IOI11_race)	C++17	100 / 100	1404 ms	62380 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=2e5+5;

vector< pair<int,int> > adj[N];
int n,k, ans=(1<<30);
int sz[N], del[N], nn;

void dfs0(int node, int pa=-1)
{
	sz[node]=1;
	nn++;
	for(auto it:adj[node]) {
	/*for(int i=0;i<adj[node].size();i++)
	{
		auto it=adj[node][i];
		if(del[it.F])
		{
			swap(adj[node][i],adj[node].back());
			adj[node].pop_back();
			i--; continue;
		}*/
		if(del[it.F] || it.F==pa) continue;
		dfs0(it.F, node);
		sz[node]+=sz[it.F];
	}
}

int find_cent(int node,int pa=-1)
{
	for(auto it:adj[node])
	{
		if(del[it.F]||it.F==pa) continue;
		if(sz[it.F]>nn/2) return find_cent(it.F, node);
	}
	return node;
}

map<long long,multiset<int>> co;

void dfs1(int node, int pa, long long len, int h, int add)
{
	if(add)
		co[len].insert(h);
	else
		co[len].erase(co[len].find(h));
	for(auto it:adj[node])
	{
		if(del[it.F]||it.F==pa) continue;
		dfs1(it.F, node, len+it.S, h+1, add);
	}
}

void dfs2(int node, int pa, long long len, int h)
{
	if(co.count(k-len))
	{
		if(co[k-len].size())
			ans=min(ans,h+(*co[k-len].begin()));
	}
	for(auto it:adj[node])
	{
		if(del[it.F]||it.F==pa) continue;
		dfs2(it.F, node, len+it.S, h+1);
	}
}

void dfs_cent(int root)
{
	nn=0; co.clear();
	dfs0(root);
	int cent=find_cent(root);
	dfs1(cent, -1, 0, 0, 1);
	for(auto it:adj[cent])
	{
		if(del[it.F]) continue;
		dfs1(it.F, cent, it.S, 1, 0);
		dfs2(it.F, cent, it.S, 1);
	}
	del[cent]=1;
	for(auto it:adj[cent])
	{
		if(!del[it.F])
			dfs_cent(it.F);
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	n=N; k=K;
	for(int i=0;i<n-1;i++)
	{
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	dfs_cent(0);
	return (ans==(1<<30)?-1:ans);
}

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