Submission #1100966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100966		alexander707070	Dreaming (IOI13_dreaming)	C++14	100 / 100	72 ms	26428 KiB

dreaming

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

#define MAXN 100007
using namespace std;

const int inf=1e9;

int n,m,len;
vector< pair<int,int> > v[MAXN];
bool vis[MAXN];
int down[MAXN],up[MAXN],mindist,maxdist;
vector<int> w;

void dfs(int x,int p){
	vis[x]=true;

	for(int i=0;i<v[x].size();i++){
		if(v[x][i].first==p)continue;
		dfs(v[x][i].first,x);

		down[x]=max(down[x],down[v[x][i].first]+v[x][i].second);
	}
}

void dfs2(int x,int p){
	vis[x]=true;

	multiset<int> s;
	for(int i=0;i<v[x].size();i++){
		if(v[x][i].first==p)continue;
		s.insert(down[v[x][i].first]+v[x][i].second);
	}

	for(int i=0;i<v[x].size();i++){
		if(v[x][i].first==p)continue;
		
		s.erase(s.find(down[v[x][i].first]+v[x][i].second));

		up[v[x][i].first]=up[x];
		if(!s.empty())up[v[x][i].first]=max(up[v[x][i].first], *s.rbegin());
		up[v[x][i].first]+=v[x][i].second;

		dfs2(v[x][i].first,x);

		s.insert(down[v[x][i].first]+v[x][i].second);
	}

	mindist=min(mindist,max(down[x],up[x]));
	maxdist=max(maxdist,max(down[x],up[x]));
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
//int travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T) {
    n=N; m=M; len=L;

	for(int i=1;i<=m;i++){
		A[i-1]++; B[i-1]++;
		v[A[i-1]].push_back({B[i-1],T[i-1]});
		v[B[i-1]].push_back({A[i-1],T[i-1]});
	}

	for(int i=1;i<=n;i++){
		if(!vis[i])dfs(i,0);
	}

	for(int i=1;i<=n;i++)vis[i]=false;

	for(int i=1;i<=n;i++){
		if(!vis[i]){
			mindist=inf; dfs2(i,0);
			w.push_back(mindist);
		}
	}

	sort(w.begin(),w.end());
	reverse(w.begin(),w.end());

	if(w.size()==1)return maxdist;
	
	if(w.size()==2){
		return max(maxdist,w[0]+w[1]+len);
	}else{
		return max(max(maxdist,w[0]+w[1]+len),w[1]+w[2]+2*len);
	}
}

/*int main(){

	cout<<travelTime(12,8,2,{0,8,2,5,5,1,1,10},{8,2,7,11,1,3,9,6},{4,2,4,3,7,1,5,3})<<"\n";
 
	return 0;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:18: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]
   18 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:30: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]
   30 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
dreaming.cpp:35: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]
   35 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

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