Submission #940886

#	Time	Username	Problem	Language	Result	Execution time	Memory
940886		Leo121	Factories (JOI14_factories)	C++17	100 / 100	4907 ms	390176 KiB

factories

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

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define mp make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define SZ(v) int(v.size())
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef long double ld;
typedef double db;
typedef long long lli;
///typedef __int128 Int;

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
///const int inf = 1e4

const int MX = 2e5;
const ll inf = 5e14;

vector<vii> tree;
vector<int> subtree_size;
vector<bool> is_removed;
vector<vector<pair<int, ll>>> ancestors;
vector<ll> di;

int get_subtree_size(int u, int p = -1) {
	subtree_size[u] = 1;
	for (auto & [v, d] : tree[u]) {
		if (v == p || is_removed[v]) continue;
		subtree_size[u] += get_subtree_size(v, u);
	}
	return subtree_size[u];
}

int get_centroid(int u, int tree_size, int p = -1) {
	for (auto & [v, d] : tree[u]) {
		if (v == p || is_removed[v]) continue;
		if (subtree_size[v] * 2 > tree_size)
			return get_centroid(v, tree_size, u);
	}
	return u;
}

void get_dists(int u, int centroid, int p, ll dist) {
	for (auto & [v, d] : tree[u]) {
		if (v == p || is_removed[v]) continue;
		get_dists(v, centroid, u, dist + ll(d));
	}
	ancestors[u].push_back({centroid, dist});
}

void build_centroid_decomp(int u = 0) {
	int centroid = get_centroid(u, get_subtree_size(u));
	for (auto & [v, d] : tree[centroid]) {
		if (is_removed[v]) continue;
		get_dists(v, centroid, centroid, ll(d));
	}

	is_removed[centroid] = 1;
	for (auto & [v, d] : tree[centroid]) {
		if (is_removed[v]) continue;
		// build the centroid decomposition for all child components
		build_centroid_decomp(v);
	}
}

///t == 1 delete the info
///t == 0 update the info with the distance
void update(int u, bool t){
    di[u] = (t) ? inf : 0;
    for(auto & [v, d] : ancestors[u]) di[v] = (t) ? inf : min(di[v], d);
}

ll query(int u){
    ll ans = di[u];
    for(auto & [v, d] : ancestors[u]) ans = min(ans, di[v] + d);
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    is_removed.assign(N, 0);
    ancestors.assign(N, vector<pair<int, ll>>());
    tree.assign(N, vii());
    subtree_size.assign(N, 0);
    for0(i, N){
        tree[A[i]].pb({B[i], D[i]});
        tree[B[i]].pb({A[i], D[i]});
    }
    build_centroid_decomp(0);
    di.assign(N, inf);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = inf;
    for0(i, S) update(X[i], 0);
    for0(i, T) ans = min(ans, query(Y[i]));
    for0(i, S) update(X[i], 1);
    return ans;
}

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