제출 #348089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348089		keta_tsimakuridze	경주 (Race) (IOI11_race)	C++14	0 / 100	153 ms	262148 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][22],par[N],ans,u,v,n,k,vis[N];
vector<int>C[N];
map<int,pair<int,int> >fix;
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][h]=d1;
	dist[1][u][h]=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 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);
//	cout<<p<<"-->"<<c<<endl;
	C[p].push_back(c);
	vis[c]=h;
	for(int i=0;i<V[c].size();i++){
		if(!vis[V[c][i].f]) new_tree(V[c][i].f,c,h+1);
	}
}
void dfs(int u,int h,int t){
	if(t==0){
	if(fix[k-dist[1][u][h]].f) ans=min(ans,dist[0][u][h]+fix[k-dist[1][u][h]].s);}
	else {
		if(!fix[dist[1][u][h]].f) fix[dist[1][u][h]].f=1 ,fix[dist[1][u][h]].s = dist[0][u][h];
		else fix[dist[1][u][h]].s=min(dist[0][u][h],fix[dist[1][u][h]].s);
	}
	for(int i=0;i<C[u].size();i++){
		dfs(C[u][i],h,t);
	}
}
int best_path(int n, int k, int H[][2], int L[]) {
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		u=H[i][0]; v=H[i][1];
		int w=L[i];
		V[u].push_back({v,w});
		V[v].push_back({u,w});
	}
	ans=4e5;
	new_tree(1,0,1);// cout<<"+";
	for(int j=1;j<=n;j++){
		for(int i=0;i<C[j].size();i++){
			dfs(C[j][i],vis[j],0);
			dfs(C[j][i],vis[j],1);
		}
		fix.clear();
	}
	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 new_tree(int, int, int)':
race.cpp:38: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]
   38 |  for(int i=0;i<V[c].size();i++){
      |              ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<C[u].size();i++){
      |              ~^~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0;i<C[j].size();i++){
      |               ~^~~~~~~~~~~~

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