Submission #821781

#	Time	Username	Problem	Language	Result	Execution time	Memory
821781		OAleksa	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#include <bits/stdc++.h>
//#include "factories.h"
#define f first
#define s second
using namespace std; 
const int maxn = 1e5 + 69;
const int lg = 18;
int up[maxn][lg];
int timer, tin[maxn], tout[maxn], sz[maxn], par[maxn], vis[maxn];
vector<pair<int, int>> g[maxn];
const long long inf = 1e18;
vector<long long> d(maxn, inf), dis(maxn);
void find_sz(int v, int p) {
	if(vis[v]) {
		sz[v] = 0;
		return;
	}
	sz[v] = 1;
	for(auto u : g[v]) {
		if(u.f != p) {
			find_sz(u.f, v);
			sz[v] += sz[u.f];
		}
	}
}

int find_cen(int v, int p, int n) {
	for(auto u : g[v]) {
		if(u.f != p && !vis[u.f] && sz[u.f] > n / 2)
			return find_cen(u.f, v, n);
	}
	return v;
}

void dfs(int v, int p) {
	find_sz(v, -1);
	int c = find_cen(v, -1, sz[v]);
	par[c] = p;
	vis[c] = 1;
	for(auto u : g[c]) {
		if(!vis[u.f])
			dfs(u.f, c);
	}
}

bool is_anc(int v,int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int lca(int a, int b) {
	if(is_anc(a, b))
		return a;
	else if(is_anc(b, a))
		return b;
	for(int i = lg - 1;i >= 0;i--) {
		if(!is_anc(up[a][i], b) && up[a][i] != -1)
			a = up[a][i];
	}
	return up[a][0];
}

long long dist(int a, int b) {
	int lc = lca(a, b);
	return dis[a] + dis[b] - 2ll * dis[lc];
}

void dfs1(int v,int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for(int i = 1;i < lg;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for(auto u : g[v]) {
		if(u.f != p) {
			dis[u.f] = dis[v] + u.s;
			dfs1(u.f, v);
		}
	}
	tout[v] = timer;
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0;i < N - 1;i++) {
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, -1);
	dfs1(0, -1);
}


long long Query(int S, int X[], int T, int Y[]) {
 	for(int i = 0;i < S;i++)
  		d[X[i]] = 0;
  	long long ans = inf;
	for(int i = 0;i < S;i++) {
		int t = X[i], y = X[i];
		while(y != -1) {
			d[y] = min(d[y], dist(t, y));
			y = par[y];
		}
	}
	for(int i = 0;i < T;i++) {
		int t = Y[i], c = Y[i];
		while(c != -1) {
			ans = min(ans, dist(c, t) + d[c]);
			c = par[c];
		}
	}
	for(int i = 0;i < S;i++) {
		int y = X[i];
		while(y != -1) {
			d[y] = inf;
			y = par[y];
		}
	}
	return ans;
}



signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		int n, q;
		cin >> n >> q;
		int a[n - 1], b[n - 1], c[n - 1];
		for(int i = 0;i < n - 1;i++)
			cin >> a[i] >> b[i] >> c[i];
		Init(n, a, b, c);
		for(int i = 0;i < q;i++) {
			int s, t;
			cin >> s >> t;
			int x[s];
			for(int j = 0;j < s;j++)
				cin >> x[j];
			int y[t];
			for(int j = 0;j < t;j++)
				cin >> y[j];
			cout << Query(s, x, t, y) << "\n";
		}
	}
   return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccmGr5wn.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccStqsto.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status