Submission #29272

#	Time	Username	Problem	Language	Result	Execution time	Memory
29272		inqr	Race (IOI11_race)	C++14	100 / 100	2016 ms	42980 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define DB printf("debug\n");
using namespace std;
int n,k,ans=1e9;
vector < pair < int , int > > ed[200005];
vector < bool > cenbef(200005,0);
vector < int  > subcnt(200005,0);
int sub_count(int vn,int vb){//kendisi dahil
	subcnt[vn]=1;
	for(int i=0;i<ed[vn].size();i++){
		int vnx=ed[vn][i].st;
		if(!cenbef[vnx]&&vnx!=vb){
			subcnt[vn]+=sub_count(vnx,vn);
		}
	}
	return subcnt[vn];
}
int find_cen(int vn,int vb,int ts){
	for(int i=0;i<ed[vn].size();i++){
		int vnx=ed[vn][i].st;
		if(!cenbef[vnx]&&vnx!=vb&&subcnt[vnx]>ts/2)
			return find_cen(vnx,vn,ts);
	}
	return vn;
}
void merge(map<int,int>&a,map<int,int>&b){
	map<int,int>::iterator it;
	for(it=b.begin();it!=b.end();it++)
		if(a.find(k-it->st)!=a.end())
			ans=min(ans,a[k-it->st]+it->nd);
	for(it=b.begin();it!=b.end();it++)
		if(a.find(it->st)==a.end())
			a[it->st]=it->nd;
		else a[it->st]=min(a[it->st],it->nd);
}
void dfs(int vn,int vb,int rn,int wn,map<int,int>&sbtm){
	if(wn>k)return;
	if(sbtm.find(wn)==sbtm.end())sbtm[wn]=rn;
	else sbtm[wn]=min(sbtm[wn],rn);
	for(int i=0;i<ed[vn].size();i++){
		int vnx=ed[vn][i].st,edw=ed[vn][i].nd;
		if(!cenbef[vnx]&&vnx!=vb)
			dfs(vnx,vn,rn+1,wn+edw,sbtm);
	}
}
void rou_find(int vn){
	map < int , int > allm;
	allm[0]=0;
	for(int i=0;i<ed[vn].size();i++){
		int vnx=ed[vn][i].st;
		int edl=ed[vn][i].nd;
		if(!cenbef[vnx]){
			map < int , int > sbtm;
			dfs(vnx,vn,1,edl,sbtm);
			merge(allm,sbtm);
		}
	}
}
void solve(int vn){
	sub_count(vn,-1);
	int cen=find_cen(vn,-1,subcnt[vn]);
	cenbef[cen]=1;
	rou_find(cen);
	for(int i=0;i<ed[cen].size();i++){
		int vnx=ed[cen][i].st;
		if(!cenbef[vnx])
			solve(vnx);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	n=N;k=K;
  	for(int i=0;i<N-1;i++){
  		ed[H[i][0]].push_back(make_pair(H[i][1],L[i]));
  		ed[H[i][1]].push_back(make_pair(H[i][0],L[i]));
  	}
  	solve(0);
  	if(ans==1e9)
  		return -1;
  	else return ans;
}

Compilation message (stderr)

race.cpp: In function 'int sub_count(int, int)':
race.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
              ~^~~~~~~~~~~~~~
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
              ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
              ~^~~~~~~~~~~~~~
race.cpp: In function 'void rou_find(int)':
race.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[vn].size();i++){
              ~^~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed[cen].size();i++){
              ~^~~~~~~~~~~~~~~

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