Submission #88008

#	Time	Username	Problem	Language	Result	Execution time	Memory
88008		Pajaraja	Race (IOI11_race)	C++17	100 / 100	1166 ms	107076 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> g[200007], w[200007];
bool vi[200007];
int x,c,p[200007],b[1000007],sol,k;
queue<pair<int,int> > q;
queue<int> qb;
void dfsbroj(int s,int f)
{
	if(vi[s]) return;
	x++;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsbroj(g[s][i],s);
}
int dfs(int s,int f)
{
	if(vi[s]) return 0;
	int k=1;
	bool moze=true;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f)
	{
	    int a=dfs(g[s][i],s);
        if(a>x/2) moze=false;
	    k+=a;
	}
	if(x-k>x/2) moze=false;
	if(moze) c=s;
	return k;
}
void dfssolve(int s,int f,int d,int dist)
{
	if(vi[s] || dist>k) return;
	q.push(make_pair(d,dist));
	qb.push(dist);
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfssolve(g[s][i],s,d+1,dist+w[s][i]);
}
void centrodecomp(int s,int f)
{
	x=0;
	dfsbroj(s,f);
	dfs(s,f);
	vi[c]=true;
	for(int i=0;i<g[c].size();i++) if(!vi[g[c][i]]) 
	{
	    dfssolve(g[c][i],c,1,w[c][i]);
	    queue<pair<int,int> > qv;
	    while(!q.empty())
	    {
	    	sol=fmin(sol,q.front().first+b[k-q.front().second]);
	    	qv.push(q.front());
	    	q.pop();
		}
		while(!qv.empty())
		{
			b[qv.front().second]=fmin(b[qv.front().second],qv.front().first);
			qv.pop();
		}
	}
	while(!qb.empty())
	{
		b[qb.front()]=100000007;
		qb.pop();
	}
	int r=c;
	for(int i=0;i<g[r].size();i++) if(!vi[g[r][i]]) centrodecomp(g[r][i],r);
}
int best_path(int N, int K, int H[][2], int L[])
{
	k=K;
	for(int i=0;i<N-1;i++)
	{
		g[H[i][0]].push_back(H[i][1]);
		w[H[i][0]].push_back(L[i]);
		g[H[i][1]].push_back(H[i][0]);
		w[H[i][1]].push_back(L[i]);
	}
	sol=100000007;
	for(int i=1;i<1000007;i++) b[i]=100000007;
	centrodecomp(0,-2);
	return (sol>N?-1:sol);
}

Compilation message (stderr)

race.cpp: In function 'void dfsbroj(int, int)':
race.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsbroj(g[s][i],s);
              ~^~~~~~~~~~~~
race.cpp: In function 'int dfs(int, int)':
race.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f)
              ~^~~~~~~~~~~~
race.cpp: In function 'void dfssolve(int, int, int, int)':
race.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfssolve(g[s][i],s,d+1,dist+w[s][i]);
              ~^~~~~~~~~~~~
race.cpp: In function 'void centrodecomp(int, int)':
race.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[c].size();i++) if(!vi[g[c][i]]) 
              ~^~~~~~~~~~~~
race.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[r].size();i++) if(!vi[g[r][i]]) centrodecomp(g[r][i],r);
              ~^~~~~~~~~~~~

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