Submission #140875

#	Time	Username	Problem	Language	Result	Execution time	Memory
140875		cfalas	Dreaming (IOI13_dreaming)	C++14	0 / 100	1080 ms	10732 KiB

dreaming

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#include "dreaming.h"

typedef pair<int, int> ii;
typedef vector<ii> vii;
vector<vii> adj;
int longest[1000000];
int ans=0;
int minm;
int maxans=0;
vector<bool> vis;
// O(N)
bool dfs(int s, int pre=-1){
	vis[s] = true;
	minm = min(minm, longest[s]);
	maxans = max(ans, maxans);
	for(int i=0;i<adj[s].size();i++){
		if(adj[s][i].F!=pre){
			ans+=adj[s][i].S;
			dfs(adj[s][i].F, s);
			ans-=adj[s][i].S;
		}
	}
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
	adj.assign(n+1, vii());
	vis.assign(n+1, false);
	// O(N)
	for(int i=0;i<m;i++){
		adj[A[i]].push_back(ii(B[i], T[i]));
		adj[B[i]].push_back(ii(A[i], T[i]));
	}
	int maxlong = 0;
	// O(N^2)
	for(int i=0;i<n;i++){
		vis.assign(n+1, false);
		maxans = 0;
		ans = 0;
		dfs(i);
		longest[i] = maxans;
		//cout<<longest[i]<<" ";
		maxlong = max(maxans, maxlong);
	}
	if(n==m+1) return maxlong;
	// O(N)
	vis.assign(n+1, false);
	ans = 0;
	//cout<<endl;
	int max1=0, max2=0;
	int max3=0;
	// O(N^2)
	for(int i=0;i<n;i++){
		if(!vis[i]){
			minm = 1000000;
			dfs(i);
			//cout<<minm<<" ";
			if(minm>max1) max3=max2, max2=max1, max1=minm;
			else if(minm>max2) max3=max2, max2=minm;
			else if(minm>max3) max3=minm;
		}
	}
	return max(max1+max2+L, max(maxlong, max2+max3+2*L));
}

Compilation message (stderr)

dreaming.cpp: In function 'bool dfs(int, int)':
dreaming.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[s].size();i++){
              ~^~~~~~~~~~~~~~
dreaming.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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