Submission #17157

#	Time	Username	Problem	Language	Result	Execution time	Memory
17157		erdemkiraz	꿈 (IOI13_dreaming)	C++98	24 / 100	122 ms	12916 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(0, x);
	//printf("mx = %d\n", mx);
	//////////////////////////////
	int A = mx;
	mx = -1;
	vec.clear();
	dfs(0, A);
	foreach(it, vec) {
		int x = *it;
		distA[x] = dist[x];
	}
	/////////////////////////////
	int B = mx;
	mx = -1;
	vec.clear();
	dfs(0, 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));
	}
	priority_queue < ii > Q;
	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("x = %d a = %d b = %d\n", x, a, b);
			Q.push(ii(-a, -b));
		}
	}
	while(Q.size() > 1) {
		int x1 = -Q.top().first;
		int y1 = -Q.top().second;
		Q.pop();
		int x2 = -Q.top().first;
		int y2 = -Q.top().second;
		Q.pop();
		if(x1 + y1 > x1 + x2 + l) {
			Q.push(ii(-(x1), -(y1)));
		}
		else if(x2 + y2 > x1 + x2 + l) {
			Q.push(ii(-(x2), -(y2)));
		}
		else {
			int n1 = max(x1, x2);
			int n2 = min(x1, x2) + l;
			if(n1 < n2)
				swap(n1, n2);
			Q.push(ii(-(n1), -(n2)));
		}
	}
	return -(Q.top().first + Q.top().second);
}

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