oj.uz

Submission #110461

# Submission time Handle Problem Language Result Execution time Memory
110461 2019-05-10T21:14:10 Z ioilolcom Dreaming (IOI13_dreaming) C++14
18 / 100
 238 ms 24312 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 node, int pnode, int target,vector<int> &path){
	if(node == target) return 1;
	for(auto &i : adj[node]) {
		if(i.first == pnode) continue;
		if(fn(i.first, node, target,path) == 0) continue;
		path.push_back(i.first);
		return 1;
	}
	return 0;
}
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;
	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);
		path.push_back(s.x);
		int sz=(int)path.size();
		int rad=diameter;
		int cur=diameter;
		d=max(d,diameter);
		for(int j=1; j<sz; j++) {
			cur-=cost[{path[j],path[j-1]}];
			rad=min(rad,max(diameter-cur,cur));
		}
		radius.push_back(rad);
	}
	int szz=(int)radius.size();
	if(szz==1) return d;
	sort(radius.rbegin(),radius.rend());

	if(szz==2) {
		//        lol=max(lol,radius[0]+radius[1]+l);
		return max(d,radius[0]+radius[1]+l);
	}
	return max(d,max(radius[0]+radius[1]+l,radius[1]+radius[2]+2*l));


}

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24244 KB Output is correct
2 Correct 238 ms 24312 KB Output is correct
3 Correct 139 ms 17160 KB Output is correct
4 Correct 23 ms 5888 KB Output is correct
5 Incorrect 19 ms 4864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24244 KB Output is correct
2 Correct 238 ms 24312 KB Output is correct
3 Correct 139 ms 17160 KB Output is correct
4 Correct 23 ms 5888 KB Output is correct
5 Incorrect 19 ms 4864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24244 KB Output is correct
2 Correct 238 ms 24312 KB Output is correct
3 Correct 139 ms 17160 KB Output is correct
4 Correct 23 ms 5888 KB Output is correct
5 Incorrect 19 ms 4864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9356 KB Output is correct
2 Correct 75 ms 9464 KB Output is correct
3 Correct 57 ms 9464 KB Output is correct
4 Correct 70 ms 9464 KB Output is correct
5 Correct 68 ms 9464 KB Output is correct
6 Correct 69 ms 10072 KB Output is correct
7 Correct 69 ms 9720 KB Output is correct
8 Correct 65 ms 9336 KB Output is correct
9 Correct 68 ms 9336 KB Output is correct
10 Correct 71 ms 9592 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 11 ms 3452 KB Output is correct
13 Correct 11 ms 3456 KB Output is correct
14 Correct 11 ms 3452 KB Output is correct
15 Correct 11 ms 3584 KB Output is correct
16 Correct 10 ms 3452 KB Output is correct
17 Correct 10 ms 3452 KB Output is correct
18 Correct 12 ms 3580 KB Output is correct
19 Correct 10 ms 3452 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 4 ms 2688 KB Output is correct
23 Correct 11 ms 3452 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24244 KB Output is correct
2 Correct 238 ms 24312 KB Output is correct
3 Correct 139 ms 17160 KB Output is correct
4 Correct 23 ms 5888 KB Output is correct
5 Incorrect 19 ms 4864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24244 KB Output is correct
2 Correct 238 ms 24312 KB Output is correct
3 Correct 139 ms 17160 KB Output is correct
4 Correct 23 ms 5888 KB Output is correct
5 Incorrect 19 ms 4864 KB Output isn't correct
6 Halted 0 ms 0 KB -