Submission #798760

#	Time	Username	Problem	Language	Result	Execution time	Memory
798760		OrazB	Factories (JOI14_factories)	C++14	18 / 100	8044 ms	145012 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, ll>
#define pb push_back
#define ff first
#define ss second

const int N = 5e5+5;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[N][20], lvl[N];
ll w[N], cur[N];
vector<pii> E[N];

// void dfs(int nd, int pr){
// 	sub[nd] = 1;
// 	for (auto i : E[nd]){
// 		if (i.ff == pr or rem[i.ff]) continue;
// 		dfs(i.ff, nd);
// 		sub[nd] += sub[i.ff];
// 	}
// }
// int centroid(int nd, int pr, int sz){
// 	for (auto i : E[nd]){
// 		if (i.ff == pr or rem[i.ff]) continue;
// 		if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
// 	}
// 	return nd;
// }
// void build(int nd, int pr){
// 	int centr = centroid(nd, 0, sub[nd]);
// 	rem[centr] = 1;
// 	par[centr] = pr;
// 	for (auto i : E[centr]){
// 		if (!rem[i.ff]){
// 			dfs(i.ff, 0);
// 			build(i.ff, centr);
// 		}
// 	}
// }
void dfs2(int nd, int pr){
	sp[nd][0] = pr;
	for (auto i : E[nd]){
		if (i.ff == pr) continue;
		lvl[i.ff] = lvl[nd]+1;
		w[i.ff] = w[nd]+i.ss;
		dfs2(i.ff, nd);
	}
}
int LCA(int u, int v){
	if (lvl[u] < lvl[v]) swap(u, v);
	int diff = lvl[u]-lvl[v];
	for (int i = 19; i >= 0; i--){
		if (diff&(1<<i)) u = sp[u][i];
	}
	if (u == v) return v;
	for (int i = 19; i >= 0; i--){
		if (sp[u][i] != sp[v][i]){
			u = sp[u][i];
			v = sp[v][i];
		}
	}
	return sp[u][0];
}
ll dist(int u, int v){
	if (u == v) return 0ll;
	return w[u]+w[v]-2*w[LCA(u,v)];
}
void Init(int n, int A[], int B[], int D[]){
	for (int i = 0; i < n-1; i++){
		A[i]++;
		B[i]++;
		E[A[i]].pb({B[i], D[i]});
		E[B[i]].pb({A[i], D[i]});
	}
	// dfs(1, 0);
	// build(1, 0);
	dfs2(1, 0);
	for (int j = 1; j <= 19; j++){
		for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1];
	}
	for (int i = 1; i <= n; i++) cur[i] = inf;
}
// void remv(int nd){
// 	while(nd){
// 		cur[nd] = inf;
// 		nd = par[nd];
// 	}
// }
// void paint(int nd){
// 	int u = nd;
// 	while(u){
// 		cur[u] = min(cur[u], dist(u, nd));
// 		u = par[u];
// 	}
// }
// ll find(int nd){
// 	ll mn = inf;
// 	int u = nd;
// 	while(u){
// 		mn = min(mn, dist(u, nd)+cur[u]);
// 		u = par[u];
// 	}
// 	return mn;
// }
ll Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++){
		X[i]++;
	// 	paint(X[i]);
	}
	ll ans = inf;
	for (int i = 0; i < T; i++){
		Y[i]++;
		// ans = min(ans, find(Y[i]));
		for (int j = 0; j < S; j++){
			ans = min(ans, dist(X[j], Y[i]));
		}
	}
	// for (int i = 0; i < S; i++) remv(X[i]);
	return ans;
}


// int main ()
// {
// 	int n, q;
// 	cin >> n >> q;
// 	int A[n], B[n], D[n];
// 	for (int i = 0; i < n-1; i++){
// 		cin >> A[i] >> B[i] >> D[i];
// 	}
// 	Init(n, A, B, D);
// 	for (int i = 0; i < q; i++){
// 		int S, T;
// 		cin >> S >> T;
// 		int X[S], Y[T];
// 		for (int j = 0; j < S; j++) cin >> X[j];
// 		for (int j = 0; j < T; j++) cin >> Y[j];
// 		cout << Query(S, X, T, Y) << '\n';
// 	}
// }		

• Subtask 1: 0 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67