Submission #17161

#	Time	Username	Problem	Language	Result	Execution time	Memory
17161		erdemkiraz	Dreaming (IOI13_dreaming)	C++98	100 / 100	158 ms	13932 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e5 + 5;

int curRoot;
vector < ii > v[N];

bool h[N];
int mx;
int dist[N], root[N];

vector < int > vec;

void dfs(int p, int x, int t = 0) {
	root[x] = curRoot;
	vec.push_back(x);
	h[x] = 1;
	dist[x] = t;
	if(mx == -1 or t > dist[mx]) {
		mx = x;
	}
	foreach(it, v[x]) {
		int u = it -> first;
		int e = it -> second;
		if(u != p)
			dfs(x, u, t + e);
	}
}

int distA[N], distB[N];

int calcLp(int x) {
	mx = -1;
	vec.clear();
	dfs(-1, x);
	//printf("mx = %d\n", mx);
	//////////////////////////////
	int A = mx;
	mx = -1;
	vec.clear();
	dfs(-1, A);
	foreach(it, vec) {
		int x = *it;
		distA[x] = dist[x];
	}
	/////////////////////////////
	int B = mx;
	mx = -1;
	vec.clear();
	dfs(-1, B);
	foreach(it, vec) {
		int x = *it;
		distB[x] = dist[x];
	}
	int mn = 2 * inf, mni = -1;
	foreach(it, vec) {
		int x = *it;
		//printf("x = %d\n", x);
		if(abs(distA[x] - distB[x]) < mn) {
			mn = abs(distA[x] - distB[x]);
			mni = x;
		}
	}
	//puts("");
	assert(mni != -1);
	return mni;
}

int f(int x) {
	if(x != root[x])
		return root[x] = f(root[x]);
	return x;
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
	for(int i = 0; i < m; i++) {
		int x = A[i];
		int y = B[i];
		int c = T[i];
		v[x].push_back(ii(y, c));
		v[y].push_back(ii(x, c));
	}
	int found = -1;
	vector < ii > vec;
	for(int i = 0; i < n; i++) {
		if(!h[i]) {
			//printf("i = %d\n", i);
			curRoot = i;
			int x = calcLp(i);
			int a = distA[x];
			int b = distB[x];
			if(a < b)
				swap(a, b);
			//printf("a = %d b = %d\n", a, b);
			vec.push_back(ii(a, b));
		}
	}
	sort(vec.begin(), vec.end());
	if(vec.size() == 1) {
		return vec[0].first + vec[0].second;
	}
	else if(vec.size() == 2){
		return max(vec[1].first + vec[1].second, vec[0].first + vec[1].first + l);
	}
	else {
		int mx = vec.back().first + vec.back().second;
		mx = max(mx, vec[vec.size() - 1].first + vec[vec.size() - 2].first + l);
		mx = max(mx, vec[vec.size() - 2].first + vec[vec.size() - 3].first + 2 * l);
		return mx;
	}
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:94:6: warning: unused variable 'found' [-Wunused-variable]
  int found = -1;
      ^~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23