Submission #332592

#	Time	Username	Problem	Language	Result	Execution time	Memory
332592		MilosMilutinovic	Race (IOI11_race)	C++14	100 / 100	578 ms	39256 KiB

race

#include "race.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define ll long int
#define pb push_back
#define mp make_pair
const int N=200050;
const int M=1000050;
const int inf=1e9;
int min(int a, int b){ return a>b?b:a;}
vector<pair<int,int> > E[N];
void AddEdge(int u, int v, int w){ E[u].pb(mp(v,w));E[v].pb(mp(u,w));}
int k;
int sz[N];
bool vis[N];
void DFS(int u, int p, int &n)
{
	n++;sz[u]=1;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		if(v!=p && !vis[v]) DFS(v,u,n),sz[u]+=sz[v];
	}
}
int Find(int u, int p, int n)
{
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		if(v!=p && !vis[v] && sz[v]>n/2) return Find(v,u,n);
	}
	return u;
}
int Find(int u){ int n=0;DFS(u,u,n);return Find(u,u,n);}
vector<pair<int,int> > bck,lzy;
int Min[M],ans=inf;
void Solve(int u, int p, int d, int w)
{
	if(w>k) return;
	bck.pb(mp(w,d));
	lzy.pb(mp(w,d));
	ans=min(ans,Min[k-w]+d);
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		int add=E[u][i].second;
		if(v!=p && !vis[v]) Solve(v,u,d+1,w+add);
	}
}
void Decompose(int u)
{
	u=Find(u);vis[u]=1;
	int i,j;
	Min[0]=0;
	lzy.pb(mp(0,0));
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		int w=E[u][i].second;
		if(!vis[v])
		{
			Solve(v,u,1,w);
			for(j=0;j<bck.size();j++) Min[bck[j].first]=min(Min[bck[j].first],bck[j].second);
			bck.clear();
		}
	}
	for(i=0;i<lzy.size();i++) Min[lzy[i].first]=inf;
	lzy.clear();
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		if(!vis[v]) Decompose(v);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	int i;k=K;int n=N;
	for(i=0;i<n-1;i++) AddEdge(H[i][0]+1,H[i][1]+1,L[i]);
	for(i=0;i<=k;i++) Min[i]=inf;
	Decompose(1);
	if(ans==inf) return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void DFS(int, int, int&)':
race.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<E[u].size();i++)
      |              ~^~~~~~~~~~~~
race.cpp: In function 'int Find(int, int, int)':
race.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<E[u].size();i++)
      |              ~^~~~~~~~~~~~
race.cpp: In function 'void Solve(int, int, int, int)':
race.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<E[u].size();i++)
      |              ~^~~~~~~~~~~~
race.cpp: In function 'void Decompose(int)':
race.cpp:57:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(i=0;i<E[u].size();i++)
      |          ~^~~~~~~~~~~~
race.cpp:64:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for(j=0;j<bck.size();j++) Min[bck[j].first]=min(Min[bck[j].first],bck[j].second);
      |            ~^~~~~~~~~~~
race.cpp:68:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(i=0;i<lzy.size();i++) Min[lzy[i].first]=inf;
      |          ~^~~~~~~~~~~
race.cpp:70:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(i=0;i<E[u].size();i++)
      |          ~^~~~~~~~~~~~

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