제출 #348237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348237		keta_tsimakuridze	경주 (Race) (IOI11_race)	C++14	100 / 100	914 ms	44524 KiB

race

#include "race.h"
#include<bits/stdc++.h>

#define f first
#define s second
using namespace std;
const int N=2e5+5;
int sz[N],dist[2][N],ans,u,v,n,k,vis[N],H;
vector<int>C[N];
pair<int,int> fix[N*10];
vector<pair<int,int> > V[N];
void find_size(int u,int p,int d,int d1,int h){
	sz[u]=1; 
	dist[0][u]=d1;
	dist[1][u]=d;
	for(int i=0;i<V[u].size();i++){
		if(!vis[V[u][i].f] && V[u][i].f!=p){
			find_size(V[u][i].f,u,d+V[u][i].s,d1+1,h);
			sz[u]+=sz[V[u][i].f];
		}
	}
}
int find_centroid(int u,int p,int Sz){
	for(int i=0;i<V[u].size();i++){
		if(!vis[V[u][i].f] && V[u][i].f!=p && Sz/2<sz[V[u][i].f]) {
			return find_centroid(V[u][i].f,u,Sz);
		}
	}
	return u;
}
void dfs(int u,int p,int t){
	if(k<dist[1][u]) return;
	if(t==0){
	if(fix[k-dist[1][u]].f==H) ans=min(ans,dist[0][u]+fix[k-dist[1][u]].s);}
	else if(t==1){
		if(fix[dist[1][u]].f!=H) fix[dist[1][u]].f=H ,fix[dist[1][u]].s = dist[0][u];
		else fix[dist[1][u]].s=min(dist[0][u],fix[dist[1][u]].s);
	}
	for(int i=0;i<V[u].size();i++){
		if(!vis[V[u][i].f] && V[u][i].f!=p)dfs(V[u][i].f,u,t);
	}
}
void new_tree(int u,int p,int h){
	find_size(u,0,0,0,h);
	int c=find_centroid(u,0,sz[u]);
	find_size(c,0,0,0,h);
	vis[c]=h; 
	fix[0].f=c;
	H=c;
		for(int i=0;i<V[c].size();i++){
			if(!vis[V[c][i].f]){
				dfs(V[c][i].f,c,0);
				dfs(V[c][i].f,c,1); 
			}
		}
		
	for(int i=0;i<V[c].size();i++){
		if(!vis[V[c][i].f]) new_tree(V[c][i].f,c,h+1);
	}
}
int best_path(int n, int K, int H[][2], int L[]) {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	k=K;
	for(int i=0;i<n-1;i++){
		u=H[i][0]; v=H[i][1];
		u++; v++; 
		int w=L[i];
		V[u].push_back({v,w});
		V[v].push_back({u,w});
	}
	ans=4e5;
	new_tree(1,0,1);
	if(ans>n)ans=-1;
	return ans;
}

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

race.cpp: In function 'void find_size(int, int, int, int, int)':
race.cpp:16: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]
   16 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:24: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]
   24 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:39: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]
   39 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
race.cpp: In function 'void new_tree(int, int, int)':
race.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=0;i<V[c].size();i++){
      |               ~^~~~~~~~~~~~
race.cpp:57: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]
   57 |  for(int i=0;i<V[c].size();i++){
      |              ~^~~~~~~~~~~~

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