Submission #94625

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94625	2019-01-21T20:57:04 Z	MvC	Race (IOI11_race)	C++11	Compilation error	0 ms	0 KB

race

#incldue "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];
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);
		vc.pb(d);
	}
	else if(rs[k-d]!=1e9)ans=min(ans,lvl+rs[k-d]);
	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)
{
	dfs_sz(root,p);
	int c=dfs_cent(root,p,sz[root]);
	cent[c]=1;
	vc.clear();
	dfs(c,p,0,0,1);
	for(int i=0;i<vc.size();i++)rs[vc[i]]=1e9;
	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++)
    {
    	x++,y++;
        cin>>x>>y>>l;
        a[x].pb({y,l});
        a[y].pb({x,l});
    }
    for(i=0;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

race.cpp:1:2: error: invalid preprocessing directive #incldue; did you mean #include?
 #incldue "race.h"
  ^~~~~~~
  include
race.cpp:111: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:51: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:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vc.size();i++)rs[vc[i]]=1e9;
              ~^~~~~~~~~~
race.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a[c].size();i++)
              ~^~~~~~~~~~~~