Submission #1265177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265177		limits	Factories (JOI14_factories)	C++20	0 / 100	2229 ms	166788 KiB

factories

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<V<pi>>;
using vvi = V<vi>;

#include "factories.h"

const ll MX = 1e17;

Adj G;

struct centroid {
	vi sz;
	V<bool> rem;
	V<V<pi>> ancs;
	V<vl> close;
	centroid() {}
	centroid(int n): sz(n), rem(n), ancs(n), close(n, vl(2, MX)) {
		build();
	}
	int get_sz(int v, int p = -1) {
		sz[v] = 1;
		for (auto &[c, w]: G[v]) if (!rem[c] && c != p) sz[v] += get_sz(c, v);
		return sz[v];
	}
	int get_centroid(int v, int n, int p = -1) {
		for (auto &[c, w]: G[v])
			if (!rem[c] && c != p && sz[c] > n/2) return get_centroid(c, n, v);
		return v;
	}
	void calc_dists(int ce, int v, int p, ll d) {
		ancs[v].pb({ce, d});
		for (auto &[c, w]: G[v]) if (!rem[c] && c != p)
			calc_dists(ce, c, v, d+w);
	}
	void build(int v = 0) {
		int ce = get_centroid(v, get_sz(v));
		for (auto &[c, w]: G[ce]) if (!rem[c]) calc_dists(ce, c, ce, w);
		rem[ce] = true;
		for (auto &[c, w]: G[ce]) if (!rem[c]) build(c);
	}

	ll upd(int v, bool typ) {
		close[v][typ] = 0;
		ll ans = close[v][!typ];
		for (auto &[p, d]: ancs[v]) {
			close[p][typ] = min(close[p][typ], (ll)d);
			ans = min(ans, close[p][typ] + close[p][!typ]);
		}
		return ans;
	}
	void reset(int v) {
		close[v][0] = close[v][1] = MX;
		for (auto &[p, d]: ancs[v]) close[p][0] = close[p][1] = MX;
	}
};

centroid cen;

void Init(int N, int A[], int B[], int D[]) {
	G = Adj(N);
	f0r(i, N-1) {
		G[A[i]].pb({B[i], D[i]});
		G[B[i]].pb({A[i], D[i]});
	}
	cen = centroid(N);
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = MX;
	f0r(i, S) cen.upd(X[i], 0);
	f0r(i, T) {
		int u = Y[i];
		ans =  min(ans, cen.close[u][0]);
		for (auto &[p, d]: cen.ancs[u]) {
			ans = min(ans, cen.close[p][0] + d);
		}
		//ans = min(ans, cen.upd(Y[i], 1));
	}
	f0r(i, S) cen.reset(X[i]);
	//f0r(i, T) cen.reset(Y[i]);
	return ans;
}

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