oj.uz

Submission #140870

# Submission time Handle Problem Language Result Execution time Memory
140870 2019-08-05T21:25:46 Z cfalas Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 12024 KB 
#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(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);
	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);
		}
	}
	return max1+max2+L;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6104 KB Output is correct
2 Incorrect 103 ms 6012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12024 KB Time limit exceeded
2 Halted 0 ms 0 KB -