제출 #101062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101062		arman_ferdous	공장들 (JOI14_factories)	C++17	100 / 100	7813 ms	258952 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int N = 5e5+10;
const int M = N*2 + 100;
const ll INF = 1e18;
 
int n;
vector< pair<int,int> > g[N];
 
int eul[M], ptr, cheats[M];
int rmq[M][20], val[M][20], pos[N];
ll lev[N], dep[N];
void lcadfs(int u, int f, ll l, int d) {
	lev[u] = l;
	dep[u] = d;
	pos[u] = ptr;
	eul[ptr++] = u;
	for(auto it : g[u]) if(it.first != f) {
		lcadfs(it.first, u, l + it.second, d + 1);
		eul[ptr++] = u;
	}
}
int lca(int u, int v) {
	if(pos[u] > pos[v]) swap(u,v);
	int k = 31 - __builtin_clz(pos[v] - pos[u]);
	if(rmq[pos[u]][k] < rmq[pos[v] - (1<<k) + 1][k]) return val[pos[u]][k];
	return val[pos[v] - (1<<k) + 1][k];
}
ll dist(int u, int v) {
	return lev[u] + lev[v] - 2ll*lev[lca(u,v)];
}
 
int Deleted[N], sub[N], head[N];
int subdfs(int u, int f) {
	sub[u] = 1;
	for(auto it : g[u]) if(it.first != f && !Deleted[it.first])
		sub[u] += subdfs(it.first, u);
	return sub[u];
}
int get_centroid(int u, int f, int lim) {
	for(auto it : g[u]) if(it.first != f && !Deleted[it.first])
		if(sub[it.first] > lim) return get_centroid(it.first, u, lim);
	return u;
}
void decompose(int s, int dad) {
	subdfs(s,-1);
	int u = get_centroid(s, -1, sub[s]/2);
	head[u] = dad;
	Deleted[u] = 1;
	for(auto it : g[u]) if(!Deleted[it.first])
		decompose(it.first, u);
}
 
ll mnDist[N]; int deNode[N];
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({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	lcadfs(0,-1,0,0);
 
 	for(int i = 1; i <= ptr; i++) cheats[i] = 31 - __builtin_clz(i);
	for(int i = 0; i < ptr; i++) {
		rmq[i][0] = dep[eul[i]];
		val[i][0] = eul[i];
	}
	for(int j = 1; j < 20; j++) {
		for(int i = 0; i + (1<<j) - 1 < ptr; i++) {
			int x = i+(1<<(j-1));
			if(rmq[i][j-1] < rmq[x][j-1]) {
				rmq[i][j] = rmq[i][j-1];
				val[i][j] = val[i][j-1];
			} else {
				rmq[i][j] = rmq[x][j-1];
				val[i][j] = val[x][j-1];
			}
		}
	}
	decompose(0,-1);
	for(int i = 0; i < n; i++)
		mnDist[i] = INF, deNode[i] = -1;
}
 
void add(int u) {
	for(int p = u; p + 1; p = head[p]) {
		ll d = dist(u, p);
		if(d < mnDist[p]) mnDist[p] = d, deNode[p] = u;
	}
}
void remove(int u) {
	for(int p = u; p + 1 && mnDist[p] != INF; p = head[p])
		mnDist[p] = INF, deNode[p] = -1;
}
ll get(int u) {
	ll ret = INF;
	for(int p = u; p + 1; p = head[p]) if(deNode[p] + 1)
		ret = min(ret, dist(u, deNode[p]));
	return ret;
}
 
ll Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) add(X[i]);
	ll ret = INF;
	for(int i = 0; i < T; i++)
		ret = min(ret, get(Y[i]));
	for(int i = 0; i < S; i++) remove(X[i]);
  	return ret;
}

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