Submission #68258

#	Time	Username	Problem	Language	Result	Execution time	Memory
68258		KLPP	Race (IOI11_race)	C++14	0 / 100	4 ms	724 KiB

race

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include "race.h" 
using namespace std;
typedef long long int lld;
typedef pair<int,lld> pii;
int dist[300000];
lld dist2[300000];
int dist3[300000];
int k,n;
bool vale[300000];
int ans;
void decompor(vector<pii> nei[],int counter){
	if(counter==0){
		return;
	}
	for(int i=0;i<n;i++)dist[i]=-1;
	for(int i=0;i<n;i++)dist2[i]=-1;
	for(int i=0;i<n;i++)dist3[i]=-1;
	for(int comeco=0;comeco<n;comeco++){
		if(dist[comeco]==-1 && vale[comeco]){
int start=comeco;
dist[start]=-2;
queue<int>q;
q.push(start);
while(!q.empty()){
	int node=q.front();q.pop();
	start=node;
	for(int i=0;i<nei[node].size();i++){
		int u=nei[node][i].first;
		if(dist[u]==-1 && vale[u]){
			dist[u]=-2;
			q.push(u);
		}
	}
}
dist[start]=0;
q.push(start);
while(!q.empty()){
	int node=q.front();q.pop();
	start=node;
	for(int i=0;i<nei[node].size();i++){
		int u=nei[node][i].first;
		if(dist[u]==-2 && vale[u]){
			dist[u]=dist[node]+1;
			q.push(u);
		}
	}
}
int centroid=start;
for(int i=0;i<dist[start]/2;i++){
	for(int j=0;j<nei[centroid].size();j++){
		if(dist[nei[centroid][j].first]<dist[centroid] && vale[nei[centroid][j].first]){
			centroid=nei[centroid][j].first;
			j=1000000;
		}
	}
}
dist2[centroid]=0;
dist[centroid]=0;
int pointer=0;
map<lld,int> m;
vector<pair<lld,int > > V;vale[centroid]=false;
//for(int i=0;i<n;i++)cout<<vale[i]<<" ";
//cout<<endl;
for(int hh=nei[centroid].size()-1;hh>-1;hh--){
	int v=nei[centroid][hh].first;
	q.push(v);
	dist3[v]=1;
	dist2[v]=nei[centroid][hh].second;
	while(!q.empty()){
		int node=q.front();q.pop();
		if(vale[node]){//cout<<node<<" ";
		V.push_back(pair<lld,int>(dist2[node],dist3[node]));
		if(dist2[node]==k && ans>=dist3[node] && vale[node]){
			ans=min(ans,dist3[node]);
			//cout<<centroid<<" P "<<node<<" "<<dist2[node]<<endl;
		}
		for(int i=0;i<nei[node].size();i++){
			int u=nei[node][i].first;
			if(dist2[u]==-1 && vale[u]){
				dist3[u]=dist3[node]+1;
				dist2[u]=dist2[node]+nei[node][i].second;
				q.push(u);
			}	
		}
		}
	}//cout<<endl;
	
	for(int i=m.size();i<V.size();i++){
		lld complemento=k-V[i].first;
		std::map<lld,int>::iterator it=m.find(complemento);
		if(it!=m.end()){//cout<<centroid<<" P "<<it->second<<" "<<V[i].second<<endl;
			if(ans>it->second+V[i].second){
				ans=min(ans,it->second+V[i].second);
				//cout<<centroid<<" "<<it->second<<" "<<V[i].second<<endl;	
			}
		}
	}
	
	for(int i=m.size();i<V.size();i++){
		std::map<lld,int>::iterator it=m.find(V[i].first);
		if(it==m.end()){
			m[V[i].first]=V[i].second;
		}else{
			int h=it->second;
			if(h>V[i].second)m[V[i].first]=V[i].second;
		}
	}
}




		}
	}//cout<<ans<<endl;
	//for(int i=0;i<n;i++)cout<<vale[i]<<" ";
	//cout<<endl;
	counter--;//cout<<endl;
	decompor(nei,counter);
}
int best_path(int N, int K, int H[][2], int L[])
{
	n=N;
	k=K;
	vector<pii >nei[n];
	for(int i=0;i<n-1;i++){
		int x,y;
		int z;
		x=H[i][0];
		y=H[i][1];
		z=L[i];
		nei[x].push_back(pair<int,lld>(y,z));
		nei[y].push_back(pair<int,lld>(x,z));
	}
	vector<int>nodes;
	for(int i=0;i<n;i++)vale[i]=true;
	ans=10000000;
	decompor(nei,30);
	//cout<<ans<<endl;
	if(ans<10000000)return ans;
	else return -1;
}
/*int main(){
	cin>>n>>k;
	vector<pii >nei[n];
	for(int i=0;i<n-1;i++){
		int x,y;
		int z;
		cin>>x>>y>>z;
		nei[x].push_back(pair<int,lld>(y,z));
		nei[y].push_back(pair<int,lld>(x,z));
	}
	vector<int>nodes;
	for(int i=0;i<n;i++)vale[i]=true;
	ans=1000000;
	decompor(nei,30);
	if(ans<1000000)cout<<ans<<endl;
	else cout<<-1<<endl;
	return 0;
}*/

Compilation message (stderr)

race.cpp: In function 'void decompor(std::vector<std::pair<int, long long int> >*, int)':
race.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<nei[node].size();i++){
              ~^~~~~~~~~~~~~~~~~
race.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<nei[node].size();i++){
              ~^~~~~~~~~~~~~~~~~
race.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<nei[centroid].size();j++){
              ~^~~~~~~~~~~~~~~~~~~~~
race.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nei[node].size();i++){
               ~^~~~~~~~~~~~~~~~~
race.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=m.size();i<V.size();i++){
                     ~^~~~~~~~~
race.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=m.size();i<V.size();i++){
                     ~^~~~~~~~~
race.cpp:64:5: warning: unused variable 'pointer' [-Wunused-variable]
 int pointer=0;
     ^~~~~~~

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