제출 #235040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235040		Blagojce	공장들 (JOI14_factories)	C++11	15 / 100	8055 ms	115836 KiB

factories

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e5 + 5;

#include "factories.h"

vector<pii> g[mxn];

int sub[mxn];
bool deleted[mxn];
int n;
int sparse[mxn][20];
ll dist[mxn];
int depth[mxn];

void dfs0(int u, int p){
	sub[u] = 1;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		dfs0(e.st, u);
		sub[u] += sub[e.st];
	}
}
int dfs1(int u, int p){
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && sub[e.st] > n / 2){
			return dfs1(e.st, u);
		}
	}
	return u;
}
void prep(int u, int p){
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i - 1]][i - 1];
	for(auto e : g[u]){
		if(e.st == p) continue;
		dist[e.st] = dist[u] + e.nd;
		depth[e.st] = depth[u] + 1;
		prep(e.st, u);
	}
	
}
int lca(int a, int b){
	int d = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[sparse[a][i]] >= d) a = sparse[a][i];
		if(depth[sparse[b][i]] >= d) b = sparse[b][i];
	}
	if(a == b){
		return a;
	}
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
ll distintree(int a, int b){
	int k = lca(a, b);
	return dist[a] + dist[b] - 2 * dist[k];
}

int parent[mxn];
ll opt[mxn];

void decompose(int root, int p){
	
	dfs0(root, root);
	n = sub[root];
	int centroid = dfs1(root, root);
	opt[centroid] = inf;
	
	
	if(root != p) parent[centroid] = p;
	else parent[centroid] = centroid;
	
	deleted[centroid] = true;
	for(auto u : g[centroid]){
		if(deleted[u.st]) continue;
		decompose(u.st, centroid);		
	}
}
	
void Init(int N, int A[], int B[], int D[]) {
	fr(i, 0, N - 1){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	decompose(0, 0);
	prep(0, 0);	
}


void update(int u){
	opt[u] = 0;
	int x = u;
	while(parent[x] != x){		
		x = parent[x];
		opt[x] = min(opt[x], distintree(x, u));
	}
}
void rupdate(int u){
	opt[u] = inf;
	int x = u;
	while(parent[x] != x){
		x = parent[x];
		opt[x] = inf;
	}
}
ll query(int u){
	ll ret = opt[u];
	int x = u;
	while(parent[x] != x){
		
		x = parent[x];
		ret = min(ret, opt[x] + distintree(x, u));
	}
	return ret;
}


ll Query(int S, int X[], int T, int Y[]) {
	fr(i, 0, S){
		update(X[i]);
	}
	
	
	ll ret = inf;
	fr(i, 0, T){
		ret = min(ret, query(Y[i]));
	}
	fr(i, 0, S){
		rupdate(X[i]);
	}
	
	return ret;
}/*
int main(){
	int N, Q;
	cin >> N >> Q; 
	int A[N], B[N], D[N];
	fr(i, 0, N - 1){	
		cin >> A[i] >> B[i] >> D[i];
	}
	Init(N, A, B, D);
	fr(i, 0, Q){
		int S, T;
		cin >> S >> T;
		int X[S], Y[T];
		fr(j, 0, S){
			cin >> X[j];
		}
		fr(j, 0, T){
			cin >> Y[j];
		}
		cout << Query(S, X, T, Y)<<endl;
		
	}
	
	

*/

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