Submission #864700

#	Time	Username	Problem	Language	Result	Execution time	Memory
864700		Lib	Dreaming (IOI13_dreaming)	C++14	100 / 100	50 ms	15612 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
vector <pair<int,int> > temp;
vector <vector <pair <int,int> > > adj;
int TreeRadius[200003];
int TreeDiameter[200003];
int check[200003];
int check2[200003];
int DistFromRoot[200003];
int DistFromEndpoint[200003];
int Previ[200003];
pair <int,int> TreeStats[200003];
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	int n,m,len,dist,s,e;
	n=N;
	m=M;
	len=L;
	for(int i=0;i<=n+1;i++){
		adj.push_back(temp);
	}
	for(int i=1;i<=m;i++){
		s=A[i-1];
		e=B[i-1];
		dist=T[i-1];
		adj[s].push_back({e,dist});
		adj[e].push_back({s,dist});
	}
	int cnt=1;
	int CFurthest;
	int CMid;
	int FirstEndpoint;
	int SecondEndpoint;
	int cur;
	vector <int> clist;
	for(int i=0;i<n;i++){
		CFurthest=0;
		CMid=1999999999;
		cur=0;
		clist.clear();
		if(check[i]==0){
			clist.push_back(i);
			check[i]=cnt;
			DistFromRoot[i]=0;
			TreeRadius[cnt]=0;
			while(cur<clist.size()){
				for(int k=0;k<adj[clist[cur]].size();k++){
					if(!check[adj[clist[cur]][k].first]){
						clist.push_back(adj[clist[cur]][k].first);
						DistFromRoot[adj[clist[cur]][k].first]=DistFromRoot[clist[cur]]+adj[clist[cur]][k].second;
						if(DistFromRoot[adj[clist[cur]][k].first] > CFurthest){
							CFurthest=DistFromRoot[adj[clist[cur]][k].first];
							FirstEndpoint=adj[clist[cur]][k].first;
						}
						check[adj[clist[cur]][k].first]=cnt;
					}
				}
				cur++;
			}
			if(clist.size()>1){
				//TreeRadius[cnt]=1999999999;
			}
			clist.push_back(FirstEndpoint);
			check2[FirstEndpoint]=cnt;
			DistFromEndpoint[FirstEndpoint]=0;
			Previ[FirstEndpoint]=-1;
			CFurthest=0;
			while(cur<clist.size()){
				for(int k=0;k<adj[clist[cur]].size();k++){
					if(!check2[adj[clist[cur]][k].first]){
						clist.push_back(adj[clist[cur]][k].first);
						DistFromEndpoint[adj[clist[cur]][k].first]=DistFromEndpoint[clist[cur]]+adj[clist[cur]][k].second;
						Previ[adj[clist[cur]][k].first]=clist[cur];
						if(DistFromEndpoint[adj[clist[cur]][k].first] > CFurthest){
							CFurthest=DistFromEndpoint[adj[clist[cur]][k].first];
							TreeRadius[cnt]=max(TreeRadius[cnt],CFurthest);
							SecondEndpoint=adj[clist[cur]][k].first;
						}
						check2[adj[clist[cur]][k].first]=cnt;
					}
				}
				cur++;
			}
			TreeDiameter[cnt]=CFurthest;
			if(TreeRadius[cnt]!=0){
				cur=SecondEndpoint;
				while(cur>-1){
					CMid=min(CMid,max(DistFromEndpoint[cur],DistFromEndpoint[SecondEndpoint]-DistFromEndpoint[cur]));
					cur=Previ[cur];
				}
				TreeRadius[cnt]=CMid;
			}
			cnt++;
		}
	}
	for(int i=1;i<cnt;i++){
		TreeStats[i]={TreeRadius[i],TreeDiameter[i]};
	}
	sort(TreeStats+1,TreeStats+cnt, greater <pair <int,int> >());
	//cout<<max(max())
	int ans=0;
	ans=TreeStats[1].second;
	if(cnt>2){
		ans=max(ans,TreeStats[1].first+TreeStats[2].first+len);
	}
	if(cnt>3){
		ans=max(ans,TreeStats[2].first+TreeStats[3].first+len*2);
	}
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    while(cur<clist.size()){
      |          ~~~^~~~~~~~~~~~~
dreaming.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int k=0;k<adj[clist[cur]].size();k++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:68:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    while(cur<clist.size()){
      |          ~~~^~~~~~~~~~~~~
dreaming.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int k=0;k<adj[clist[cur]].size();k++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:88:77: warning: 'SecondEndpoint' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |      CMid=min(CMid,max(DistFromEndpoint[cur],DistFromEndpoint[SecondEndpoint]-DistFromEndpoint[cur]));
      |                                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23