Submission #140903

#	Time	Username	Problem	Language	Result	Execution time	Memory
140903		cfalas	Dreaming (IOI13_dreaming)	C++14	18 / 100	1064 ms	12152 KiB

dreaming

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

typedef pair<long long, long long> ii;
typedef vector<ii> vii;
vector<vii> adj;
long long longest[1000000];
long long ans=0;
long long minm;
long long maxans=0;
vector<bool> vis;
// O(N)
bool dfs(long long s, long long pre=-1){
	vis[s] = true;
	if(minm==-1) minm = longest[s];
	else minm = min(minm, longest[s]);
	maxans = max(ans, maxans);
	for(long long 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(long long 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]));
	}
	long long maxlong = 0;
	// O(N^2)
	for(long long 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;
	long long max1=0, max2=0;
	long long max3=0;
	// O(N^2)
	for(long long i=0;i<n;i++){
		if(!vis[i]){
			minm = -1;
			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;
		}
	}
	if(n-m-1>=3)
	return max(max1+max2+L, max(maxlong, max2+max3+2*L));
	else
		return max(max1+max2+L, maxlong);
}

Compilation message (stderr)

dreaming.cpp: In function 'bool dfs(long long int, long long int)':
dreaming.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long i=0;i<adj[s].size();i++){
                    ~^~~~~~~~~~~~~~
dreaming.cpp:28: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: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23