Submission #96746

# Submission time Handle Problem Language Result Execution time Memory
96746 2019-02-11T16:57:27 Z figter001 Dreaming (IOI13_dreaming) C++14
14 / 100
1000 ms 11128 KB
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5;

vector<pair<int,int>> g[maxn];
bool vis[maxn],idx[maxn];
vector<int> c;
int sz[maxn],mx,to,used[maxn],cst[maxn][2],t,best,mn;

void path(int u,int cost){
	idx[u] = vis[u] = 1;
	if(cost > mx){
		mx = cost;
		to = u;
	}
	for(pair<int,int> cur : g[u]){
		int v = cur.first;
		int w = cur.second;
		if(vis[v])continue;
		path(v,cost + w);
	}
}

void dfs(int u,int cost){
	vis[u] = 1;
	cst[u][t] = cost;
	if(t == 1){
		if(max(cst[u][0],cst[u][1]) < mn){
			mn = max(cst[u][0],cst[u][1]);
			best = u;
		}
	}
	for(pair<int,int> cur : g[u]){
		int v = cur.first;
		int w = cur.second;
		if(vis[v])continue;
		dfs(v,cost + w);
	}	
}

void find(int s){
	mn = 2e9;
	mx = 0;
	memset(vis,0,sizeof(vis));
	path(s,0);
	t = 0;
	memset(vis,0,sizeof(vis));
	dfs(to,0);
	memset(vis,0,sizeof(vis));
	mx = 0;
	path(to,0);
	t = 1;
	memset(vis,0,sizeof(vis));
	dfs(to,0);
	s = best;
	c.push_back(s);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i=0;i<M;i++){
		g[A[i]].push_back({B[i],T[i]});
		g[B[i]].push_back({A[i],T[i]});
	}
	for(int i=0;i<N;i++)
		if(!idx[i])
			find(i);
	for(int i=1;i<c.size();i++){
		g[c[i]].push_back({c[0],L});
		g[c[0]].push_back({c[i],L});
	}
	memset(vis,0,sizeof(vis));
	mx = 0;
	path(0,0);
	memset(vis,0,sizeof(vis));
	mx = 0;
	path(to,0);
    return mx;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<c.size();i++){
              ~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 75 ms 11128 KB Output is correct
2 Correct 71 ms 11128 KB Output is correct
3 Correct 42 ms 8568 KB Output is correct
4 Correct 12 ms 4092 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 20 ms 4728 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 39 ms 6136 KB Output is correct
9 Correct 47 ms 7416 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 77 ms 8696 KB Output is correct
12 Correct 109 ms 9916 KB Output is correct
13 Correct 6 ms 2936 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2812 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 4 ms 2808 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 4 ms 2808 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 4 ms 2808 KB Output is correct
14 Correct 4 ms 2808 KB Output is correct
15 Incorrect 4 ms 2808 KB Output isn't correct
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 65 ms 11088 KB Output is correct
2 Correct 60 ms 11128 KB Output is correct
3 Correct 43 ms 8480 KB Output is correct
4 Correct 11 ms 4088 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 3 ms 2808 KB Output is correct
9 Correct 3 ms 2808 KB Output is correct
10 Correct 3 ms 2808 KB Output is correct
11 Correct 4 ms 2808 KB Output is correct
12 Correct 3 ms 2808 KB Output is correct
13 Correct 4 ms 2808 KB Output is correct
14 Correct 4 ms 2808 KB Output is correct
15 Correct 4 ms 2808 KB Output is correct
16 Correct 4 ms 2808 KB Output is correct
17 Correct 4 ms 2808 KB Output is correct
18 Correct 3 ms 2808 KB Output is correct
19 Correct 86 ms 10104 KB Output is correct
20 Correct 97 ms 10104 KB Output is correct
21 Correct 124 ms 10196 KB Output is correct
22 Correct 103 ms 10232 KB Output is correct
23 Correct 88 ms 10104 KB Output is correct
24 Correct 82 ms 10152 KB Output is correct
25 Correct 79 ms 9848 KB Output is correct
26 Incorrect 107 ms 9948 KB Output isn't correct
27 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 7760 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB Output is correct
2 Correct 11 ms 2936 KB Output is correct
3 Correct 14 ms 3064 KB Output is correct
4 Incorrect 7 ms 2808 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 11 ms 2936 KB Output is correct
3 Correct 14 ms 2936 KB Output is correct
4 Correct 274 ms 8284 KB Output is correct
5 Correct 347 ms 9604 KB Output is correct
6 Incorrect 7 ms 2808 KB Output isn't correct
7 Halted 0 ms 0 KB -