oj.uz

Submission #234107

# Submission time Handle Problem Language Result Execution time Memory
234107 2020-05-23T07:07:40 Z cfalas Dreaming (IOI13_dreaming) C++14
0 / 100
 80 ms 22776 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#include "dreaming.h"

typedef pair<long long, long long> ii;
typedef vector<ii> vii;
vector<vii> adj;
#define ll long long

vector<bool> vis;
vector<ii> leafdist;
vector<ii> h1, h2;

vector<int> longest;
vector<int> comp;

int component=0;
ii diam(int s, int p=-1, int dist=0){
	//cout<<s<<" "<<p<<endl;
	vis[s] = true;
	ii l = {0, s}, t;
	longest[s] = max(longest[s], dist);
	comp[s] = component;
	for(auto x : adj[s]) if(x.F!=p) t = diam(x.F, s, dist+x.S), l = max(l, ii(x.S + t.F, t.S));
	leafdist[s] = l;
	return l;
}


int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
	adj.assign(n+1, vii());
	vis.assign(n+1, false);
	leafdist.assign(n+1, ii(0,0));
	longest.assign(n+1, 0);
	comp.assign(n+1, 0);
	for(long long 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]));
	}
	ll ans=0;
	int cnt=0;
	for(int i=0;i<n;i++){
		if(vis[i]) continue;
		//cout<<"crap\n";
		component = ++cnt;
		int root = diam(i).S;
		//cout<<"============= "<<root<<" ============\n";
		ii root2 = diam(root);
		ans = max(ans, root2.F);
		diam(root2.S);

		// Find center;

	}
	vii center(cnt-1, ii(-1000000,1000000));
	for(int i=0;i<n;i++){
		//cout<<i<<" "<<longest[i]<<endl;
		if(-center[comp[i]-1].F>longest[i]) center[comp[i]-1] = ii(-longest[i], i);
	}
	//for(int i=0;i<center.size();i++) cout<<i<<" "<<center[i].F<<endl;
	sort(center.begin(), center.end());
	if(center.size()>=2) ans = max(ans, -center[0].F-center[1].F + L);
	return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 22648 KB Output is correct
2 Correct 80 ms 22776 KB Output is correct
3 Correct 55 ms 15188 KB Output is correct
4 Correct 13 ms 3584 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 21 ms 5504 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 22648 KB Output is correct
2 Correct 80 ms 22776 KB Output is correct
3 Correct 55 ms 15188 KB Output is correct
4 Correct 13 ms 3584 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 21 ms 5504 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 22648 KB Output is correct
2 Correct 80 ms 22776 KB Output is correct
3 Correct 55 ms 15188 KB Output is correct
4 Correct 13 ms 3584 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 21 ms 5504 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8448 KB Output is correct
2 Incorrect 41 ms 8488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 22648 KB Output is correct
2 Correct 80 ms 22776 KB Output is correct
3 Correct 55 ms 15188 KB Output is correct
4 Correct 13 ms 3584 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 21 ms 5504 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 22648 KB Output is correct
2 Correct 80 ms 22776 KB Output is correct
3 Correct 55 ms 15188 KB Output is correct
4 Correct 13 ms 3584 KB Output is correct
5 Correct 11 ms 2048 KB Output is correct
6 Correct 21 ms 5504 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -