Submission #364720

#	Time	Username	Problem	Language	Result	Execution time	Memory
364720		ogibogi2004	경주 (Race) (IOI11_race)	C++14	0 / 100	13 ms	19948 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
const int MAXK=1e6+6;
const int lg=21;
vector<pair<int,ll> >g[MAXN];
vector<int>g1[MAXN];
int n,k;
vector<int>dfs_order;
ll depth[MAXN],depth1[MAXN];
int wherel[MAXN],wherer[MAXN];
pair<int,int> dp[3*MAXN][lg];
int pw[3*MAXN];
bool f[MAXN];
int st[MAXN],root;
ll minh[MAXK],ans=n+2;
int rankc[MAXN];
vector<int>updated;
void dfs(int u,int p)
{
	dfs_order.push_back(u);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		depth[v.first]=depth[u]+1;
		depth1[v.first]=depth1[u]+v.second;
		dfs(v.first,u);
		dfs_order.push_back(u);
	}
}
void precompute()
{
	int t=1,cnt=0;
	for(int i=1;i<3*MAXN;i++)
	{
		if(t*2<=i)
		{
			t*=2;cnt++;
		}
		pw[i]=cnt;
	}
	for(int i=0;i<dfs_order.size();i++)
	{
		wherer[dfs_order[i]]=i;
	}
	for(int i=dfs_order.size()-1;i>=0;i--)
	{
		wherel[dfs_order[i]]=i;
	}
	for(int i=0;i<dfs_order.size();i++)
	{
		dp[i][0]={depth[dfs_order[i]],dfs_order[i]};
	}
	for(int step=1;step<lg;step++)
	{
		for(int i=0;i<dfs_order.size();i++)
		{
			dp[i][step]=dp[i][step-1];
			if(i+(1<<(step-1))<dfs_order.size())
			{
				dp[i][step]=min(dp[i][step],dp[i+(1<<(step-1))][step-1]);
			}
		}
	}
}
int lca(int x,int y)
{
	if(wherel[x]>wherel[y])swap(x,y);
	pair<int,int>ret;
	int i1=wherel[x],i2=wherer[y];
	int d=i2-i1+1;
	int l=pw[d];
	ret=dp[i1][l];
	ret=min(ret,dp[i2-(1<<l)+1][l]);
	return ret.second;
}
void dfs1(int u,int p)
{
	st[u]=1;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		dfs1(v.first,u);
		st[u]+=st[v.first];
	}
}
int find(int u,int p,int t)
{
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		if(st[v.first]>t/2)
		{
			find(v.first,u,t);
		}
	}
	return u;
}
void decompose(int u,int p)
{
	dfs1(u,p);
	int c=find(u,p,st[u]);
	if(p!=-1)
	{
		rankc[c]=rankc[p]+1;
		g1[p].push_back(c);
	}
	else 
	{
		root=c;
		rankc[c]=1;
	}
	f[c]=1;
	for(auto v:g[c])
	{
		if(f[v.first])continue;
		decompose(v.first,c);
	}
}
void dfs2(int u,int p,int maxrank,int d,int d1)
{
	minh[d1]=min(minh[d1],(ll)d);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(rankc[v.first]>=maxrank)continue;
		if(v.second+d1>k)continue;
		dfs2(v.first,u,maxrank,d+1,d1+v.second);
	}
}
void dfs3(int u,int p,int maxrank,int d,int d1)
{
	ans=min(ans,minh[k-d1]+d);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(rankc[v.first]>=maxrank)continue;
		if(v.second+d1>k)continue;
		dfs3(v.first,u,maxrank,d+1,d1+v.second);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	n=N;k=K;
	for(int i=0;i<N-1;i++)
	{
		g[H[i][0]+1].push_back({H[i][1]+1,L[i]});
		g[H[i][1]+1].push_back({H[i][0]+1,L[i]});
	}
	dfs(1,0);
	precompute();
	decompose(1,-1);
	for(int i=0;i<MAXK;i++)minh[i]=n+2;
	for(int i=1;i<=n;i++)
	{
		minh[0]=0;
		updated.push_back(0);
		for(auto v:g[i])
		{
			if(rankc[v.first]>=rankc[i])continue;
			if(v.second>k)continue;
			dfs3(v.first,i,rankc[i],1,v.second);
			dfs2(v.first,i,rankc[i],1,v.second);
		}
		for(auto u:updated)minh[u]=n+2;
	}
	if(ans>n)return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void precompute()':
race.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
race.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
race.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i=0;i<dfs_order.size();i++)
      |               ~^~~~~~~~~~~~~~~~~
race.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    if(i+(1<<(step-1))<dfs_order.size())
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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