Submission #16585

#	Time	Username	Problem	Language	Result	Execution time	Memory
16585		comet	Race (IOI11_race)	C++98	100 / 100	1030 ms	29296 KiB

race

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAX_N 200000
#define MAX_K 1000000

struct edge{int u,c;};

typedef vector<edge> vec;
typedef vector<vec> mat;
mat path;

int n,comet,SubSz[MAX_N],MaxSz[MAX_N];
bool killed[MAX_N];
bool chk[MAX_N];
vector<int> s;

int dfs(int v){
	chk[v]=1;
	s.push_back(v);
	int ret=0;
	SubSz[v]=MaxSz[v]=1;
	for(int i=0;i<path[v].size();i++){
		int u=path[v][i].u;
		if(killed[u]||chk[u])continue;
		ret=dfs(u);
		SubSz[v]+=ret;
		MaxSz[v]=max(MaxSz[v],ret+1);
	}
	chk[v]=0;
	return SubSz[v];
}

int centroid(int v){

	s.clear();
	dfs(v);
	int x,ret=v,Max=0;
	for(int i=0;i<s.size();i++){
		x=s[i];

		if(Max<min(SubSz[v]-MaxSz[x],MaxSz[x])){
			Max=min(SubSz[v]-MaxSz[x],MaxSz[x]);
			ret=x;
		}
	}
	return ret;
}

int stamp[MAX_K+1],a[MAX_K+1];
struct state{int v,c,len;};

int f(int v){

	int root=centroid(v);
	killed[root]=1;

	int ret=1e9;

	for(int i=0;i<path[root].size();i++){
		int u=path[root][i].u;
		if(killed[u])continue;

		queue<state> Q;
		Q.push(state{u,path[root][i].c,1});
		chk[u]=1;

		while(!Q.empty()){
			state h=Q.front();
			Q.pop();
			if(h.c==comet)ret=min(ret,h.len);
			if(h.c>=comet)continue;
			if(stamp[comet-h.c]==root)ret=min(ret,a[comet-h.c]+h.len);
			for(int j=0;j<path[h.v].size();j++){
				int uu=path[h.v][j].u;
				if(killed[uu]||chk[uu])continue;
				chk[uu]=1;
				Q.push(state{uu,h.c+path[h.v][j].c,h.len+1});
			}
		}
		Q.push(state{u,path[root][i].c,1});
		chk[u]=0;
		while(!Q.empty()){
			state h=Q.front();
			Q.pop();
			if(h.c>=comet)continue;
			if(stamp[h.c]==root)
				a[h.c]=min(a[h.c],h.len);
			else
				stamp[h.c]=root,a[h.c]=h.len;
			for(int j=0;j<path[h.v].size();j++){
				int uu=path[h.v][j].u;
				if(killed[uu]||chk[uu]==0)continue;
				chk[uu]=0;
				Q.push(state{uu,h.c+path[h.v][j].c,h.len+1});
			}
		}
	}

	for(int i=0;i<path[root].size();i++){
		int u=path[root][i].u;
		if(killed[u])continue;
		ret=min(ret,f(u));
	}

	killed[root]=0;
	return ret;
}

int best_path(int N, int K, int H[][2], int L[]){
	memset(stamp,-1,sizeof(stamp));
	n=N;
	comet=K;
	path.assign(n,vec());
	for(int i=0;i<n;i++){
		path[H[i][0]].push_back(edge{H[i][1],L[i]});
		path[H[i][1]].push_back(edge{H[i][0],L[i]});
	}
	int ret=f(0);
	return ret==1e9?-1:ret;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int)':
race.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path[v].size();i++){
              ~^~~~~~~~~~~~~~~
race.cpp: In function 'int centroid(int)':
race.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
race.cpp: In function 'int f(int)':
race.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path[root].size();i++){
              ~^~~~~~~~~~~~~~~~~~
race.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<path[h.v].size();j++){
                ~^~~~~~~~~~~~~~~~~
race.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<path[h.v].size();j++){
                ~^~~~~~~~~~~~~~~~~
race.cpp:104:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path[root].size();i++){
              ~^~~~~~~~~~~~~~~~~~

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