Submission #676461

#	Time	Username	Problem	Language	Result	Execution time	Memory
676461		penguin133	Factories (JOI14_factories)	C++17	100 / 100	5487 ms	243012 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<ll, pi>
#define fi first
#define se second
#define getchar_unlocked getchar_nolock


ll n, m, q;
vector<pi>v[500005];
vector<ll> ct[500005];
ll dep[500005], par[20][500005], sz[500005], vis[500005];
ll dist[500005][20];
ll mn[500005];
ll di[5000005];
void dfs(int x, int p, int d){
	sz[x] = 1;
	for(auto [i, j] : v[x]){
		if(i == p || vis[i])continue;
		dfs(i, x, d + 1);
		sz[x] += sz[i];
	}
}
int rt, lim;
int cent(int x, int p){
	for(auto [i, j] : v[x]){
		if(i == p || vis[i])continue;
		if(sz[i] * 2 > lim)return cent(i, x);
	}
	return x;
}
int lvl = 1;
void dfs2(int x, int p, ll cur){
	dist[x][lvl] = cur;
	for(auto [i, j] : v[x]){
		if(i == p || vis[i])continue;
		dfs2(i, x, cur + j);
	}
}

void proc(int x, int p){
	par[0][x] = p;
	dep[x] = (p == -1 ? 0 : dep[p]) + 1;
	for(auto i : ct[x])if(i != p)proc(i, x);
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i=0;i<N-1;i++)A[i]++, B[i]++, v[A[i]].push_back({B[i], D[i]}), v[B[i]].push_back({A[i], D[i]});
	dfs(1, -1, 1);
	lim = N;
	int x = cent(1, -1);
	rt = x;
	queue<pi>qu;
	qu.push({x, 1});
	//cerr << rt << '\n';
	vis[x] = 1;
	while(!qu.empty()){
		x = qu.front().fi;
		int y = qu.front().se; qu.pop();
		vis[x] = 1;
		lvl = y;
		dfs2(x, -1, 0);
		for(auto [i, j] : v[x]){
			if(vis[i])continue;
			dfs(i, x, 1);
			lim = sz[i];
			int lmao = cent(i, x);
			ct[x].push_back(lmao);
			ct[lmao].push_back(x);
			//cerr << "ADDING EDGE " << x << " " << lmao << "\n";
			qu.push({lmao, y + 1});
		}
	}
	assert(lvl <= 20);
	proc(rt, -1);
	for(int i=1;i<=N;i++)mn[i] = 1e18;
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int>tmp;
	for(int i=0;i<S;i++)X[i]++;
	for(int i=0;i<T;i++)Y[i]++;
	for(int i=0;i<T;i++){
		int ori = Y[i];
		mn[ori] = 0;
		while(ori != -1){
			mn[ori] = min(mn[ori], dist[Y[i]][dep[ori]]);
			tmp.push_back(ori);
			ori = par[0][ori];
		}
	}
	ll ans =  1e18;
	for(int i=0;i<S;i++){
		ll ans2 = mn[X[i]], ori = X[i];
		while(ori != -1){
			ans2 = min(ans2, mn[ori] + dist[X[i]][dep[ori]]);
			ori = par[0][ori];
		}
		ans = min(ans, ans2);
	}
	for(auto i : tmp)mn[i] = 1e18;
  return ans;
}

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