Submission #546793

#	Time	Username	Problem	Language	Result	Execution time	Memory
546793		lovrot	Dreaming (IOI13_dreaming)	C++11	Compilation error	0 ms	0 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 = 1000000010;
const int INF = 1e9 + 10;

int n, m, l;
int min_max[MN], c[MN];
int nxt[MN], maxp[MN], h[MN], nxte[MN];

bool mark[MN], bio[MN];

vector<pii> g[MN];
vector<int> used; 
set<int> s;
 
int Find(int x){ 
	//cout << x << " +\n";
	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;
		}
	}

	//cout << x << " " << maxp[x] << " " << mi << "\n";

	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 s = maxp[x]; 
 	int zb = 0;

 	if(printp){ 
 		return {s, 0};
 	}

	int mn = INF, mni = x; 
	while(x != y){ 
		if(mn > max(zb, s - zb)){ 
			mn = max(zb, s - zb);
			mni = x;
		}	
		//cout << x << " -> " << nxt[x] << " (" << nxte[x] << " " << zb << ")\n";
		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;
	}
 
	//cin >> n >> m >> l;
 	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;
		//cin >> 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);
		
		c[*it] = res.X;
		min_max[*it] = res.Y;

		it++;
	}

	while(s.size() > 1){
		auto it = s.begin(); 
		int a = *it;
		it++; 
		int b = *it;

		int ca = c[a], av = min_max[a];
		int cb = c[b], bv = min_max[b]; 
		
		s.erase(a);
		s.erase(b);
		Union(a, b);
		g[ca].pb({cb, l});
		g[cb].pb({ca, l});

		int nh = Find(a);
		s.insert(nh);

		if(max(av, bv + l) > max(bv, av + l)){
			swap(ca, cb);
			swap(av, bv);
		}
		c[nh] = ca;
		min_max[nh] = max(av, bv + l);
	}
	pii ret = findCenter(*(s.begin()), 1);
	return ret.X;
}
/*
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;
}*/

Compilation message (stderr)

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status