제출 #928203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928203		oblantis	공장들 (JOI14_factories)	C++17	0 / 100	389 ms	524288 KiB

factories

//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll inf = 1e16;
const int mod = 1e9+7;
const int maxn = 5e5 + 1;
#include "factories.h"
int dp[maxn], up[maxn][20], sz[maxn], cup[maxn];
ll p[maxn], dst[maxn];
vt<pii> g[maxn];
vt<int> rst;
bool first;
void dfs(int v){
	sz[v] = 1;
	for(auto i : g[v]){
		if(i.ff != up[v][0]){
			up[i.ff][0] = v;
			dp[i.ff] = dp[v] + 1;
			p[i.ff] = p[v] + i.ss;
			dfs(i.ff);
			sz[v] += sz[i.ff];
		}
	}
}
void cd(int v, int m){
	for(auto i : g[v]){
		if(sz[i.ff] > m / 2){
			sz[v] = m - sz[i.ff];
			cd(i.ff, m);
			return;
		}
	}
	if(!first){
		first = 1;
		cup[v] = -1;
	}
	sz[v] = -1;
	for(auto i : g[v]){
		if(sz[i.ff] != -1){
			cup[i.ff] = v;
			cd(i.ff, sz[i.ff]);
		}
	}
}
void dist(int x, int y, ll& q){
	if(dp[x] > dp[y])swap(x, y);
	int a = x, b = y;
	for(int j = 19; j >= 0; j--){
		if(((dp[b] - dp[a]) >> j) & 1){
			b = up[b][j];
		}
	}
	if(a == b){
		q = p[x] - p[a] + p[y] - p[a];
		return;
	}
	for(int j = 19; j >= 0; j--){
		if(up[b][j] != up[a][j]){
			a = up[a][j], b = up[b][j];
		}
	}
	a = up[a][0];
	q = p[x] - p[a] + p[y] - p[a];
}
void Init(int n, int a[], int b[], int d[]) {
	for(int i = 0; i < n - 1; i++){
		g[a[i]].pb({b[i], d[i]});
		g[b[i]].pb({a[i], d[i]});
	}
	dfs(0);
	for(int j = 1; j < 20; j++){
		for(int i = 0; i < n; i++)up[i][j] = up[up[i][j - 1]][j - 1];
	}
	cd(0, n);
	for(int i = 0; i < n; i++)dst[i] = inf;
}
void upd(int v, int i){
	if(v == -1)return;
	if(dst[v] == inf){
		rst.pb(v);
	}
	ll path;
	dist(i, v, path);
	dst[v] = min(dst[v], path);
	upd(cup[v], i);
}
void get(int v, int i, ll& ret){
	if(v == -1)return;
	ll path;
	dist(i, v, path);
	ret = min(ret, path + dst[v]);
	get(cup[v], i, ret);
}
long long Query(int s, int x[], int t, int y[]) {
	ll ret = inf;
	for(int i = 0; i < s; i++){
		upd(x[i], x[i]);
	}
	for(int i = 0; i < t; i++){
		get(y[i], y[i], ret);
	}
	for(auto i : rst)dst[i] = inf;
	rst.clear();
	return ret;
}

//void solve() {
	//int n, q;
	//cin >> n >> q;
	//int a[n - 1], b[n - 1], d[n - 1];
	//for(int i = 0; i < n - 1; i++){
		//cin >> a[i] >> b[i] >> d[i];
	//}
	//Init(n, a, b, d);
	//for(int i = 0; i < q; i++){
		//int s, t;
		//cin >> s >> t;
		//int x[s], y[t];
		//for(int j = 0; j < s; j++)cin >> x[j];
		//for(int j = 0; j < t; j++)cin >> y[j];
		//cout << Query(s, x, t, y) << '\n';
	//}
//}
//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}

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