Submission #1311136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311136		Nomio	Factories (JOI14_factories)	C++20	0 / 100	31 ms	4840 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define s second
#define f first
#define pii pair<int, long long>

using namespace std;
using ll = long long;
const int maxn = 1e6 + 1;

bool removed[maxn] {};
int sz[maxn] {};
vector<pii> adj[maxn];

int get_sz(int u, int p) {
	sz[u] = 1;
	for(pii P : adj[u]) {
		int v = P.f;
		if(removed[v] || v == p) continue;
		sz[u] += get_sz(v, u);
	}
	return sz[u];
}

int get_centroid(int u, int p, int sze) {
	for(pii P : adj[u]) {
		int v = P.f;
		if(removed[v] || v == p) continue;
		if(sz[v] > sze / 2) return get_centroid(v, u, sze);
	}
	return u;
}

map<pair<int, int>, ll> anc;

void get_dist(int u, int p, int cent, ll dist) {
	for(pii P : adj[u]) {
		int v = P.f;
		ll w = P.s;
		if(removed[v] || v == p) continue;
		get_dist(v, u, cent, dist + w);
	}
	anc[{cent, u}] = dist;
}

vector<pii> ch[maxn];
vector<int> par(maxn, -1);

int build_centroid(int u) {
	get_sz(u, -1);
	int center = get_centroid(u, -1, sz[u]);
	removed[center] = 1;
	for(pii P : adj[center]) {
		int v = P.f;
		ll w = P.s;
		if(removed[v]) continue;
		get_dist(v, center, center, w);
		int V = build_centroid(v);
		par[V] = center;
		ch[center].push_back({V, anc[{center, V}]});
	}
	return center;
}

int lvl[maxn] {};
ll dis[maxn] {};

void dfs(int u) {
	for(pii P : ch[u]) {
		int v = P.f;
		ll w = P.s;
		lvl[v] = lvl[u] + 1;
		dis[v] = dis[u] + w;
		dfs(v);
	}
}

int LCA(int u, int v) {
	if(lvl[u] < lvl[v]) swap(u, v);
	while(lvl[u] > lvl[v]) {
		u = par[u];
	}
	while(u != v) {
		u = par[u];
		v = par[v];
	}
	return u;
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N - 1; i++) {
		adj[A[i]].push_back({B[i], 1LL * D[i]});
		adj[B[i]].push_back({A[i], 1LL * D[i]});
	}
	int center = build_centroid(0);
	dis[center] = 0;
	dfs(center);
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = 1e18;
	for(int i = 0; i < S; i++) {
		for(int j = 0; j < T; j++) {
			int c = LCA(X[i], Y[j]);
			ans = min(ans, dis[X[i]] + dis[Y[j]] - dis[c] * 2);
		}
	}
	return ans;
}

//int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
//	cout << Query(1, {2}, 1, {5}) << '\n';
//	return 0;
//}

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