Submission #234107

#	Time	Username	Problem	Language	Result	Execution time	Memory
234107		cfalas	Dreaming (IOI13_dreaming)	C++14	0 / 100	80 ms	22776 KiB

dreaming

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23