Submission #26580

#	Time	Username	Problem	Language	Result	Execution time	Memory
26580		rubabredwan	Factories (JOI14_factories)	C++14	100 / 100	5826 ms	205268 KiB

factories

/*  Bismillahir Rahmanir Rahim  */
 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
typedef pair <int, int> pii;
 
const int N = 500005;
const long long oo = 1e18;
 
vector < vector <pii>> g(N);
vector < int > e[N];
long long mn[N], dis[N];
long long pre[N][25], idx[N];
int n, anc[N], sub[N], vis[N];	

void dfs(int at, int par){
	pre[at][++idx[at]] = dis[at];
	sub[at] = 1;
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		dis[u.first] = dis[at] + u.second;
		dfs(u.first, at);
		sub[at] += sub[u.first];
	}
}

void decompose(int at, int par, int tot){
	int cen = 0, mx = -1;
	for(auto u : g[at]){
		if(vis[u.first] || sub[u.first] > sub[at]) continue;
		if(sub[u.first] > mx){
			cen = u.first;
			mx = sub[cen];
		}
	}
	if(mx <= tot / 2){
		if(par){
			anc[at] = par;
		}
		tot = 0;
		vis[at] = 1;
		dis[at] = 0;
		dfs(at, at);
		for(auto u : g[at]){
			if(!vis[u.first]){ 
				decompose(u.first, at, sub[u.first]);
			}
		}
	}
	else decompose(cen, par, tot);
}

long long Query(int S, int X[], int T, int Y[]){	
	int cur, from, j;
	for(int i = 0; i < S; ++i){
		cur = X[i] + 1, from = X[i] + 1, j = 1;
		for(j = idx[from]; j; --j){
			mn[cur] = min(mn[cur], pre[from][j]);
			cur = anc[cur];
		}
	}
	long long ret = oo;
	for(int i = 0; i < T; ++i){
		cur = Y[i] + 1, from = Y[i] + 1, j = 1;
		for(j = idx[from]; j; --j){
			ret = min(ret, pre[from][j] + mn[cur]);
			cur = anc[cur];
		}
	}
	for(int i = 0; i < S; ++i){
		cur = X[i] + 1;
		while(cur) mn[cur] = oo, cur = anc[cur];
	}
	return ret;
}
 
void Init(int N, int A[], int B[], int D[]){
	n = N;
	for(int i = 0; i < N - 1; ++i){
		g[A[i] + 1].push_back({B[i] + 1, D[i]});
		g[B[i] + 1].push_back({A[i] + 1, D[i]});
	}
	memset(idx, -1, sizeof(idx));
	dfs(1, 0);
	decompose(1, 0, sub[1]);
	for(int i = 1; i <= n; ++i) mn[i] = oo;
}

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