Submission #546832

#	Time	Username	Problem	Language	Result	Execution time	Memory
546832		lovrot	Dreaming (IOI13_dreaming)	C++11	100 / 100	190 ms	19812 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
 
#define X first
#define Y second
#define pii pair<int, int> 
#define pb push_back
 
using namespace std;
 
const int MN = 100010;
const int INF = 2 * 1e9 + 10;


int n, m, l, ret;
int min_max[MN], c[MN];
int nxt[MN], maxp[MN], h[MN], nxte[MN];
 
bool mark[MN], bio[MN];
 
vector<pii> g[MN], v;
vector<int> used; 
set<int> s;

bool comp(pii a, pii b){
	return a.Y > b.Y;	
}

int Find(int x){ 
	if(h[x] == x)
		return x;
	return h[x] = Find(h[x]);
}
 
void Union(int x, int y){ 
	h[x] = Find(y);
}
 
void use(int x){ 
	if(!mark[x]){ 
		used.pb(x);
		mark[x] = true;
	}
}
 
int maxPath(int x){
	use(x);
	bio[x] = true;
	maxp[x] = 0;
	int mi = x;
	for(pair<int, int> e : g[x]){
		int y = e.X;
		if(bio[y])
			continue;
 
		int val = e.Y; 
		int f = maxPath(y);
		if(maxp[y] + val > maxp[x]){ 
			maxp[x] = maxp[y] + val;
			mi = f;
			nxt[x] = y;
			nxte[x] = val;
		}
	}
 
	return mi;
}
 
void clearUsed(){ 
	for(int x : used){
		nxt[x] = 0;
		maxp[x] = 0;
		mark[x] = false;
		bio[x] = 0;
		nxte[x] = 0;
	}
	used.clear();
}
 
pii findCenter(int x, bool printp){ 
	clearUsed();
	x = maxPath(x);	
	clearUsed();
	int y = maxPath(x);
 
	int p = maxp[x]; 
	ret = max(ret, p);
 	int zb = 0;
 
 	if(printp){ 
 		return {p, 0};
 	}
 
	int mn = p, mni = x; 
	while(x != y){ 
		if(mn > max(zb, p - zb)){ 
			mn = max(zb, p - zb);
			mni = x;
		}	
		zb += nxte[x]; 
		x = nxt[x];
	}
 
	if(mn == INF)
		mn = 0;
 
	return {mni, mn};
}
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	ios_base::sync_with_stdio(false);
	
	for(int i = 0; i < MN; i++){
		h[i] = i;
		c[i] = i;
	}
 
	n = N;
 	m = M;
 	l = L;
 
	for(int i = 0; i < n; i++)
		s.insert(i);
 
	for(int i = 0; i < m; i++){ 
		int a, b, t;
		a = A[i];
 		b = B[i]; 
 		t = T[i];
 
		g[a].push_back({b, t});
		g[b].push_back({a, t});
		a = Find(a);
		b = Find(b);
		
		s.erase(a);
		s.erase(b);
		Union(a, b);
		s.insert(Find(a));
	}
 	
	auto it = s.begin();
	while(it != s.end()){ 
		pii res = findCenter(*it, 0);
		
		v.pb(res);

		it++;
	}
 	
 	sort(v.begin(), v.end(), comp);

	if(v.size() > 1)
		ret = max(ret, v[0].Y + v[1].Y + l);
	if(v.size() > 2)
		ret = max(ret, v[1].Y + v[2].Y + l * 2);
	return ret;
}
/*
int main(){ 
	int n, m, l;
	int a[MN], b[MN], t[MN]; 

	cin >> n >> m >> l;

	for(int i = 0; i < m; i++)
		cin >> a[i] >> b[i] >> t[i];

	cout << travelTime(n, m, l, a, b, t) << "\n";
	return 0;
}*/

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