Submission #140768

#	Time	Username	Problem	Language	Result	Execution time	Memory
140768		cfalas	꿈 (IOI13_dreaming)	C++14	0 / 100	53 ms	12796 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[10000];
int ans=0;
int minm;
int maxans=0;
vector<bool> vis;
set<int> tree;
// O(NlogN)
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(!vis[adj[s][i].F]){
			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]));
	}
	// O(N^2logN)
	for(int i=0;i<n;i++){
		vis.assign(n+1, false);
		maxans = 0;
		ans = 0;
		dfs(i);
		longest[i] = maxans;
		//cout<<longest[i]<<" ";
	}
	// O(N)
	vis.assign(n+1, false);
	tree.clear();
	ans = 0;
	//cout<<endl;
	vector<int> treeans;
	int max1=0, max2=0;
	// O(N^2logN)
	for(int i=0;i<n;i++){
		if(!vis[i]){
			minm = 1000000;
			dfs(i);
			//cout<<minm<<" ";
			if(minm>max1) max2=max1, max1=minm;
			else if(minm>max2) max2=minm;
			treeans.push_back(minm);
			tree.clear();
		}
	}
	return max1+max2+L;
}

Compilation message (stderr)

dreaming.cpp: In function 'bool dfs(int, int)':
dreaming.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int 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: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23