제출 #331509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331509		SavicS	경주 (Race) (IOI11_race)	C++14	100 / 100	888 ms	43832 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;
//isto
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);
}

//isto
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);
}

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

race.cpp: In function 'void dfsbroj(int, int)':
race.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  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:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  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:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  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:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<g[c].size();i++) if(!vi[g[c][i]])
      |              ~^~~~~~~~~~~~
race.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  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