Submission #387500

#	Time	Username	Problem	Language	Result	Execution time	Memory
387500		saarang123	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KiB

factories

#include <bits/stdc++.h>
#ifndef saarang
#include "factories.h"
#endif
using namespace std;
std::mt19937 rng(15);
const int mxn = 500 * 1000 + 3, lgn = 20;
int up[mxn][lgn], d[mxn], par[mxn], sz[mxn], n, og;
long long dt[mxn], ans[mxn];
vector<array<int, 2>> g[mxn];
bool cent[mxn];

void dfs(int v, int p) {
	up[v][0] = (p < 0 ? v : p);
	for(auto &[u, w] : g[v]) if(u != p) {
		d[u] = d[v] + 1;
		dt[u] = dt[v] + w;
		dfs(u, v);
	}
	for(int i = 1; i < lgn; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
}

int kth(int v, int di) {
	for(int i = 0; i < lgn; i++)
		if(di >> i & 1)
			v = up[v][i];
	return v;
}

int lca(int a, int b) {
	if(d[a] > d[b])
		swap(a, b);
	b = kth(b, d[b] - d[a]);
	if(a == b) return a;
	for(int i = lgn - 1; i >= 0; i--)
		if(up[a][i] != up[b][i])
			a = up[a][i], b = up[b][i];
	return up[a][0];
}

long long dist(int a, int b) { return dt[a] + dt[b] - 2 * dt[lca(a, b)]; }

int dfssz(int v, int p) {
	sz[v] = 1;
	for(auto &[u, w] : g[v]) if(u != p && !cent[u])
		sz[v] += dfssz(u, v);
	return sz[v];
}

int fcent(int v, int p) {
	for(auto &[u, w] : g[v]) if(u != p && !cent[u]) {
		if(sz[u] > sz[og] / 2)
			return fcent(u, v);
	}
	return v;
}

void decompose(int v, int p) {
	dfssz(v, -1);
	int centroid = fcent(og = v, -1);
	cent[centroid] = true;
	par[centroid] = p;
	for(auto &[u, w] : g[centroid])
		if(u != p && !cent[u]) 
			decompose(u, centroid);
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	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);
	decompose(0, -1);
	for(int i = 0; i <= n; i++)
        ans[i] = 1'000'000'000'000'000'000;
}

void upd(int v) {
	for(int p = v; p != -1; p = par[p]) 
		ans[p] = min(ans[p], dist(p, v));
}

void fix(int v) {
	for(int p = v; p != -1; p = par[p])
		ans[p] = ans[n];
}

long long query(int v) {
	long long res = ans[n];
	for(int p = v; p != -1; p = par[p])
		res = min(res, ans[p] + dist(p, v));
	return res;
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < T; i++)
		upd(Y[i]);
	long long answer = ans[n];
	for(int i = 0; i < S; i++)
		answer = min(answer, query(X[i]));
	for(int i = 0; i < T; i++)
		fix(Y[i]);
	return answer;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    int N, Q;
    cin >> N >> Q;
    int A[N - 1], B[N - 1], D[N - 1];
    for(int i = 0; i < N - 1; i++) 
    	cin >> A[i] >> B[i] >> D[i];
    Init(N, A, B, D);
    while(Q--) {
    	int S, T;
    	cin >> S >> T;
    	int X[S], Y[T];
    	for(int i = 0; i < S; i++)
    		cin >> X[i];
    	for(int i = 0; i < T; i++)
    		cin >> Y[i];
    	cout << Query(S, X, T, Y) << '\n';
    }
    return 0;
}

Compilation message (stderr)

/tmp/ccMYjinn.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccDCOMIS.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status