Submission #527632

#	Time	Username	Problem	Language	Result	Execution time	Memory
527632		NekoRolly	Factories (JOI14_factories)	C++17	100 / 100	3459 ms	170304 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+4;
const ll inf = 1e18;

struct Cd{
	vector<pair<int,int>> adj[N];
	int sz[N],up[N],h[N],vis[N];
	ll dis[N][19],val[N];

	int find(int u,int p,int Sz){
		int val = 0,x = 0; sz[u] = 1;
		for (auto [v, w] : adj[u]) if (v != p && !vis[v]){
			x ^= find(v, u, Sz); sz[u] += sz[v];
			val = max(val, sz[v]);
		}
		if (max(val, Sz-sz[u]) <= Sz/2) up[x = u] = p;
		return x;
	}

	void dfs(int u,int p,int H){
		for (auto [v, w] : adj[u]) if (v != p && !vis[v]){
			dis[v][H] = dis[u][H] + w;
			dfs(v, u, H);
		}
	}

	void build(int u,int p,int Sz){
		u = find(u, -1, Sz);
		if (up[u] != -1) sz[up[u]] = Sz-sz[u];
		vis[u] = 1, h[u] = h[p]+1, up[u] = p, val[u] = inf;
		dfs(u, -1, h[u]);
		for (auto [v, w] : adj[u]) if (!vis[v])
			build(v, u, sz[v]);
	}

	void upd(int u,bool f){
		for (int v=u; v; v=up[v]){
			if (f) val[v] = min(val[v], dis[u][h[v]]);
			else val[v] = inf;
		}
	}

	ll que(int u){
		ll ans = inf;
		for (int v=u; v; v=up[v]) ans = min(ans, dis[u][h[v]] + val[v]);
		return ans;
	}
} d;


void Init(int n, int A[], int B[], int D[]) {
	for (int i=0; i<n-1; i++){
		d.adj[++A[i]].push_back({++B[i], D[i]});
		d.adj[B[i]].push_back({A[i], D[i]});
	}

	d.h[0] = -1;
	d.build(1, 0, n);
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i=0; i<S; i++) d.upd(++X[i], 1);
	ll ans = inf;
	for (int i=0; i<T; i++) ans = min(ans, d.que(++Y[i]));
	for (int i=0; i<S; i++) d.upd(X[i], 0);
	return ans;
}

/*
int n,q,S,T;
int A[N],B[N],D[N],X[N],Y[N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;

	for (int i=0; i+1<n; i++) cin >> A[i] >> B[i] >> D[i];

	Init(n, A, B, D);

	while (q--){
		cin >> S >> 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;
}
*/

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