제출 #94632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94632		MvC	경주 (Race) (IOI11_race)	C++11	100 / 100	496 ms	45388 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];
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[])
{
  k=K;
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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++)
              ~^~~~~~~~~~~~

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