oj.uz

Submission #110450

# Submission time Handle Problem Language Result Execution time Memory
110450 2019-05-10T21:03:26 Z ioilolcom Dreaming (IOI13_dreaming) C++14
14 / 100
 336 ms 27384 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define y second
#define x  first
#define ll long long int
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=1e5+7;
vector<pair<int,int> > adj[N];
bool vis[N];
void dfs(int node,int p,int length,pii &ans){
	vis[node]=1;
	for(auto vertice:adj[node]) {
		if(vertice.x==p) {
			continue;
		}
		dfs(vertice.x,node,length+vertice.y,ans);
	}
	if(length>ans.y) {
		ans.x=node;
		ans.y=length;
	}
}
bool fn(int s,int e,int p,vector<int> &path){
	if(s==e) {
		return true;
	}
	for(auto v:adj[s]) {
		if(v.x==p) continue;
		if(fn(v.x,e,s,path)) {
			path.push_back(v.x);
			return true;
		}
	}
	return false;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	int n=N;
	int m=M;
	int l=L;
	vector<int> radius;
	map<pair<int,int>,int> cost;
	for(int i=0; i<M; i++) {
		int u=A[i];
		int v=B[i];
		int w=T[i];
		adj[u].pb({v,w});
		adj[v].pb({u,w});
		cost[{u,v}]=cost[{v,u}]=w;
	}
	int d=0;
	vector<pii> ans;
	for(int i=0; i<n; i++) {
		if(vis[i]) continue;
		pii s={-1,-1};
		dfs(i,-1,0,s);
		pii e={-1,-1};
		dfs(s.first,-1,0,e);
		int diameter=e.y;
		vector<int> path;
		fn(s.x,e.x,0,path);
		int sz=(int)path.size();
		int radius=diameter;
		int center=i;
		int cur=diameter;
		d=max(d,diameter);
		for(int j=1; j<sz; j++) {
			cur-=cost[{path[j],path[j-1]}];
			int vv=max(diameter-cur,cur);
			if(vv<radius) {
				center=path[j];
				radius=vv;
			}
		}
		ans.push_back({center,radius});
	}

	int node=0;
	int mx=-1;
	for(auto v:ans) {
		if(v.y>mx) {
			node=v.x;
			mx=v.y;
		}
	}
	for(auto v:ans) {
		if(v.x!=node) {
			//edges.push_back({v.f,node});
			adj[v.x].push_back({node,l});
			adj[node].push_back({v.x,l});
		}
	}
	pii z={-1,-1};
	dfs(1,0,0,z);
	pii zz={-1,-1};
	dfs(z.x,0,0,zz);
	return zz.y;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:40:6: warning: unused variable 'm' [-Wunused-variable]
  int m=M;
      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 27380 KB Output is correct
2 Correct 274 ms 27384 KB Output is correct
3 Correct 162 ms 18808 KB Output is correct
4 Correct 27 ms 6372 KB Output is correct
5 Correct 20 ms 4864 KB Output is correct
6 Correct 42 ms 8056 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 119 ms 11920 KB Output is correct
9 Correct 145 ms 15352 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 261 ms 19320 KB Output is correct
12 Correct 336 ms 23416 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 27380 KB Output is correct
2 Correct 274 ms 27384 KB Output is correct
3 Correct 162 ms 18808 KB Output is correct
4 Correct 27 ms 6372 KB Output is correct
5 Correct 20 ms 4864 KB Output is correct
6 Correct 42 ms 8056 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 119 ms 11920 KB Output is correct
9 Correct 145 ms 15352 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 261 ms 19320 KB Output is correct
12 Correct 336 ms 23416 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 4 ms 2688 KB Output is correct
16 Correct 4 ms 2688 KB Output is correct
17 Correct 4 ms 2688 KB Output is correct
18 Correct 3 ms 2688 KB Output is correct
19 Incorrect 4 ms 2688 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 27380 KB Output is correct
2 Correct 274 ms 27384 KB Output is correct
3 Correct 162 ms 18808 KB Output is correct
4 Correct 27 ms 6372 KB Output is correct
5 Correct 20 ms 4864 KB Output is correct
6 Correct 42 ms 8056 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 119 ms 11920 KB Output is correct
9 Correct 145 ms 15352 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 261 ms 19320 KB Output is correct
12 Correct 336 ms 23416 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 4 ms 2688 KB Output is correct
16 Correct 4 ms 2688 KB Output is correct
17 Correct 4 ms 2688 KB Output is correct
18 Correct 3 ms 2688 KB Output is correct
19 Incorrect 4 ms 2688 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 11012 KB Output is correct
2 Correct 74 ms 10996 KB Output is correct
3 Correct 83 ms 10992 KB Output is correct
4 Correct 87 ms 10960 KB Output is correct
5 Correct 81 ms 10992 KB Output is correct
6 Correct 86 ms 12012 KB Output is correct
7 Correct 90 ms 11380 KB Output is correct
8 Correct 76 ms 10868 KB Output is correct
9 Correct 96 ms 10732 KB Output is correct
10 Correct 95 ms 11288 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 17 ms 7540 KB Output is correct
13 Correct 16 ms 7544 KB Output is correct
14 Correct 15 ms 7540 KB Output is correct
15 Correct 16 ms 7544 KB Output is correct
16 Correct 15 ms 7540 KB Output is correct
17 Correct 16 ms 7412 KB Output is correct
18 Correct 15 ms 7540 KB Output is correct
19 Correct 16 ms 7540 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Incorrect 4 ms 2688 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 27380 KB Output is correct
2 Correct 274 ms 27384 KB Output is correct
3 Correct 162 ms 18808 KB Output is correct
4 Correct 27 ms 6372 KB Output is correct
5 Correct 20 ms 4864 KB Output is correct
6 Correct 42 ms 8056 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 119 ms 11920 KB Output is correct
9 Correct 145 ms 15352 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 261 ms 19320 KB Output is correct
12 Correct 336 ms 23416 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 4 ms 2816 KB Output is correct
15 Correct 6 ms 2944 KB Output is correct
16 Correct 6 ms 3072 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 5 ms 2944 KB Output is correct
19 Correct 20 ms 3200 KB Output is correct
20 Correct 4 ms 2816 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Correct 7 ms 3200 KB Output is correct
23 Correct 4 ms 2688 KB Output is correct
24 Correct 4 ms 2688 KB Output is correct
25 Correct 3 ms 2688 KB Output is correct
26 Correct 4 ms 2688 KB Output is correct
27 Correct 3 ms 2688 KB Output is correct
28 Correct 4 ms 2688 KB Output is correct
29 Correct 3 ms 2688 KB Output is correct
30 Correct 4 ms 2688 KB Output is correct
31 Incorrect 4 ms 2688 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 27380 KB Output is correct
2 Correct 274 ms 27384 KB Output is correct
3 Correct 162 ms 18808 KB Output is correct
4 Correct 27 ms 6372 KB Output is correct
5 Correct 20 ms 4864 KB Output is correct
6 Correct 42 ms 8056 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 119 ms 11920 KB Output is correct
9 Correct 145 ms 15352 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 261 ms 19320 KB Output is correct
12 Correct 336 ms 23416 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 4 ms 2688 KB Output is correct
16 Correct 4 ms 2688 KB Output is correct
17 Correct 4 ms 2688 KB Output is correct
18 Correct 3 ms 2688 KB Output is correct
19 Incorrect 4 ms 2688 KB Output isn't correct
20 Halted 0 ms 0 KB -