Submission #384177

#	Time	Username	Problem	Language	Result	Execution time	Memory
384177		Aryan_Raina	Factories (JOI14_factories)	C++14	100 / 100	6464 ms	191508 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MXN = 5e5+9, LGN = 20;
const ll INF = 1e17;
ll n, sz[MXN], lvl[MXN], par[MXN], dist[LGN][MXN];
bool dead[MXN];
vector<ar<ll,2>> g[MXN];
vector<ll> d(MXN, INF);

void get_sz(int u, int pu) {
	sz[u] = 1;
	for (auto v : g[u]) if (v[1] != pu && !dead[v[1]]) {
		get_sz(v[1], u);
		sz[u] += sz[v[1]];
	}
}
int centroid(int u, int pu, int rt) {
	for (auto v : g[u]) if (v[1] != pu && !dead[v[1]]) {
		if (sz[v[1]] > sz[rt]/2) return centroid(v[1], u, rt);
	}
	return u;
}
int OneCentroid (int rt) { get_sz(rt, rt); return centroid(rt, rt, rt); }

void get_dist(int u, int pu, int l) {
	for (auto v : g[u]) if (v[1] != pu && !dead[v[1]]) {
		dist[l][v[1]] = dist[l][u]+v[0];
		get_dist(v[1], u, l);
	}
}

void decompose(int start, int pcent, int l) {
	int cent = OneCentroid(start);
	lvl[cent] = l;
	par[cent] = pcent;
	dist[l][cent] = 0;
	get_dist(cent, cent, l);
	dead[cent] = 1;
	for (auto v : g[cent]) if (!dead[v[1]]) decompose(v[1], cent, l+1); 
	dead[cent] = 0;
}

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

void add(int x, bool remove) {
	for (int u = x; u >= 0; u = par[u]) {
		if (remove) d[u] = INF;
		else d[u] = min(d[u], dist[lvl[u]][x]);
	}
}

ll qry(int x) {
	ll ans = INF;
	for (int u = x; u >= 0; u = par[u]) {
		ans = min(ans, d[u] + dist[lvl[u]][x]);
	}
	return ans;
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) add(X[i], 0);
	ll ans = INF;
	for (int i = 0; i < T; i++) ans = min(ans, qry(Y[i]));
	for (int i = 0; i < S; i++) add(X[i], 1);
	return ans;
}

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