Submission #1128496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128496		Nonoze	Factories (JOI14_factories)	C++20	15 / 100	7465 ms	525036 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
const int inf = 1e18;

const signed LOG=18;


signed n;
vector<pair<signed, signed>> adj[500005];
unordered_map<signed, int> dists[500005];


signed sz[500005], par[500005];
bool centro[500005];

void dfs(signed u, signed p) {
	sz[u]=1;
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
		dfs(v, u);
		sz[u]+=sz[v];
	}
}

signed centroid(signed u, signed p, signed obj) {
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
		if (sz[v]*2>=obj) return centroid(v, u, obj);
	}
	return u;
}

void calc(signed u, signed p, int d, signed c) {
	dists[c][u]=d;
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
		calc(v, u, d+w, c);
	}
}

signed decompose(signed u, signed p) {
	if (centro[u]) return u;
	dfs(u, u);
	signed c=centroid(u, u, sz[u]); centro[c]=1;
	par[c]=p; calc(c, c, 0, c);
	for (auto [v, w]: adj[c]) if (!centro[v]) {
		decompose(v, c);
	}
	return c;
}

int distres[500005];

void update(signed u, signed changing) {
	if (u==-1) return;
	cmin(distres[u], dists[u][changing]);
	update(par[u], changing);
}

void reset(signed u, signed changing) {
	if (u==-1) return;
	distres[u]=inf;
	reset(par[u], changing);
}

int query(signed u, signed changing) {
	if (u==-1) return inf;
	return min(distres[u]+dists[u][changing], query(par[u], changing));
}

void Init(signed N, signed A[], signed B[], signed D[]) {
	n=N;
	for (int i=0; i<n-1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
		distres[i]=inf, centro[i]=0;
	}
	distres[n-1]=inf, centro[n-1]=0;
	decompose(0, -1);
}

int Query(signed S, signed X[], signed T, signed Y[]) {
	int ans=inf;
	for (int i=0; i<S; i++) update(X[i], X[i]);
	for (int i=0; i<T; i++) cmin(ans, query(Y[i], Y[i]));
	for (int i=0; i<S; i++) reset(X[i], X[i]);
	return ans;
}

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