Submission #94628

#	Time	Username	Problem	Language	Result	Execution time	Memory
94628		MvC	Race (IOI11_race)	C++11	0 / 100	21 ms	23800 KiB

race

#include "race.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int x,y,i,n,cent[nmax],sz[nmax],k,ans=1e9,rs[nmax],f[nmax],cnt;
vector<pair<int,int> >a[nmax];
vector<int>vc;
void dfs_sz(int u,int p)
{
	sz[u]=1;
	for(int i=0;i<a[u].size();i++)
	{
		int v=a[u][i].fr;
		if(cent[v] || v==p)continue;
		dfs_sz(v,u);
		sz[u]+=sz[v];
	}
}
int dfs_cent(int u,int p,int siz)
{
	for(int i=0;i<a[u].size();i++)
	{
		int v=a[u][i].fr;
		if(cent[v] || v==p)continue;
		if(sz[v]>siz/2)return dfs_cent(v,u,siz);
	}
	return u;
}
void dfs(int x,int p,int d,int lvl,int kp)
{
	if(d>k)return;
	if(kp)
	{
		rs[d]=min(rs[d],lvl);
		if(rs[d]>lvl || f[d]<cnt)f[d]=cnt,rs[d]=lvl;
	}
	else 
	{
		if(f[k-d]==cnt && rs[k-d]!=1e9)ans=min(ans,lvl+rs[k-d]);
		if(d==k && lvl<ans)ans=lvl;
	}
	for(int i=0;i<a[x].size();i++)
	{
		int y=a[x][i].fr,v=a[x][i].sc;
		if(y==p || cent[y])continue;
		if(!lvl)
		{
			dfs(y,x,d+v,lvl+1,0);
			dfs(y,x,d+v,lvl+1,1);
		}
		else dfs(y,x,d+v,lvl+1,kp);
	}
}
void decompose(int root,int p=-1)
{
	++cnt;
	dfs_sz(root,p);
	if(sz[root]<=1)return;
	int c=dfs_cent(root,p,sz[root]);
	cent[c]=1;
	dfs(c,p,0,0,1);
	for(int i=0;i<a[c].size();i++)
	{
		int v=a[c][i].fr;
		if(cent[v])continue;
		decompose(v,c);
	}
}
int best_path(int n,int k,int h[][2],int l[])
{
	for(i=0;i<n-1;i++)
    {
    	x=h[i][0]+1,y=h[i][1]+1;
    	int lt=l[i];
        a[x].pb(pair<int,int>(y,lt));
        a[y].pb(pair<int,int>(x,lt));
    }
    for(i=0;i<=k;i++)rs[i]=1e9;
    decompose(1);
    if(ans==1e9)return -1;
    else return ans;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    cin>>n>>k;
    for(i=1;i<n;i++)
    {
		int l;
        cin>>x>>y>>l;
        x++,y++;
        a[x].pb({y,l});
        a[y].pb({x,l});
    }
    for(i=1;i<=k;i++)rs[i]=1e9;
    decompose(1);
    if(ans==1e9)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

Compilation message (stderr)

race.cpp:116:1: warning: "/*" within comment [-Wcomment]
 /*
  
race.cpp: In function 'void dfs_sz(int, int)':
race.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[u].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'int dfs_cent(int, int, int)':
race.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[u].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[x].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'void decompose(int, int)':
race.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[c].size();i++)
              ~^~~~~~~~~~~~

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