Submission #170343

#	Time	Username	Problem	Language	Result	Execution time	Memory
170343		ngmh	Factories (JOI14_factories)	C++11	100 / 100	4260 ms	196028 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pi;

#define f first
#define s second;

ll n, m, a, b, d, v, par[500005], sub[500005], ban[500005], ans[500005], dst[500005][19];
vector<pi> adj[500005];
stack<ll> st;

ll dfs1(ll u, ll p, ll l){
	sub[u] = 1;
	for(auto it : adj[u]){
		if(ban[it.f] != -1) continue;
		if(it.f == p) continue;
		if(l) dst[it.f][l-1] = dst[u][l-1]+it.s;
		sub[u] += dfs1(it.f, u, l);
	}
	return sub[u];
}

ll dfs2(ll u, ll p, ll n){
	for(auto it : adj[u]){
		if(ban[it.f] != -1) continue;
		if(it.f != p && sub[it.f] > n/2){
			return dfs2(it.f, u, n);
		}
	}
	return u;
}

void build(ll u, ll p, ll l){
	ll n = dfs1(u, p, l);
	ll cent = dfs2(u, p, n);
	if(p == -1) p = cent;
	par[cent] = p;
	ban[cent] = l;
	for(auto it : adj[cent]){
		if(ban[it.f] != -1) continue;
		dst[it.f][l] = it.s;
		build(it.f, cent, l+1);
	}
}

void update(ll x){
	ll lvl = ban[x];
	ll y = x;
	while(lvl != -1){
		ans[y] = min(ans[y], dst[x][lvl]);
		st.push(y);
		y = par[y];
		lvl--;
	}
}

ll query(ll x){
	ll res = LLONG_MAX/3;
	ll lvl = ban[x];
	ll y = x;
	while(lvl != -1){
		res = min(res, ans[y]+dst[x][lvl]);
		y = par[y];
		lvl--;
	}
	return res;
}

void Init(int N, int A[], int B[], int D[]) {
	memset(ban, -1, sizeof(ban));
    n = N;
	for(ll i = 0; i < n-1; i++){
	    a = A[i]; b = B[i]; d = D[i];
		adj[a].push_back(pi(b, d));
		adj[b].push_back(pi(a, d));
	}
	build(0, -1, 0);
	for(ll i = 0; i < n; i++) ans[i] = LLONG_MAX/3;
}

ll Query(int S, int X[], int T, int Y[]) {
    for(ll i = 0; i < S; i++) update(X[i]);
    v = LLONG_MAX;
    for(ll i = 0; i < T; i++) v = min(v, query(Y[i]));
    while(!st.empty()){ ans[st.top()] = LLONG_MAX/3; st.pop(); }
    return v;
}

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