Submission #44260

#	Time	Username	Problem	Language	Result	Execution time	Memory
44260		szawinis	Factories (JOI14_factories)	C++17	100 / 100	5952 ms	460600 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e17;
 
int n;
vector<int> sz, nxt;
vector<vector<pair<int,int> > > g;
vector<vector<ll> > d;
vector<bool> block;
vector<ll> mn;
 
void init_dfs(int u, int par, ll curr_dist = 0) {
	d[u].push_back(curr_dist);
	sz[u] = 1;
	for(auto p: g[u]) {
		int v, w; tie(v, w) = p;
		if(block[v] || v == par) continue;
		init_dfs(v, u, curr_dist + w);
		sz[u] += sz[v];
	}
}
 
void calc(int src, int par) {
	int cen = src;
	while(true) {
		bool found = false;
		for(auto p: g[cen]) if(sz[p.first] < sz[cen] && sz[p.first] << 1 >= sz[src]) {
			cen = p.first;
			found = true;
			break;
		}
		if(!found) break;
	}
	block[cen] = true;
	nxt[cen] = par;
	init_dfs(cen, -1);
	// cout << cen << ' ' << nxt[cen] << endl;
	for(auto p: g[cen]) if(!block[p.first]) calc(p.first, cen);
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	g.resize(n), sz.resize(n), nxt.resize(n), d.resize(n), block.resize(n);
	mn.assign(n, INF);
	for(int i = 0; i < n-1; i++) {
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	init_dfs(0, -1);
	calc(0, -1);
}
 
ll Query(int S, int X[], int T, int Y[]) {
	ll ret = INF;
	for(int i = 0; i < S; i++) for(int j = d[X[i]].size()-1, v = X[i]; j > 0; j--, v = nxt[v])
		mn[v] = min(d[X[i]][j], mn[v]);
	for(int i = 0; i < T; i++) for(int j = d[Y[i]].size()-1, v = Y[i]; j > 0; j--, v = nxt[v])
		ret = min(mn[v] + d[Y[i]][j], ret);
	for(int i = 0; i < S; i++) for(int j = d[X[i]].size()-1, v = X[i]; j > 0; j--, v = nxt[v])
		mn[v] = INF;
	return ret;
}

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