Submission #235054

#	Time	Username	Problem	Language	Result	Execution time	Memory
235054		Blagojce	Factories (JOI14_factories)	C++11	100 / 100	4974 ms	179024 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][20];

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 dfs3(int u, int p, int dep){
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		dist[e.st][dep] = dist[u][dep] + e.nd;
		dfs3(e.st, u, dep);
	}
}

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

void decompose(int root, int p, int dep){
	
	dfs0(root, root);
	n = sub[root];
	int centroid = dfs1(root, root);
	opt[centroid] = inf;

	depth[centroid] = dep;
	dfs3(centroid, centroid, dep);
	
	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, dep + 1);		
	}
}
	
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, 0);
}


void update(int u){
	opt[u] = 0;
	int x = u;
	while(parent[x] != x){		
		x = parent[x];
		opt[x] = min(opt[x], dist[u][depth[x]]);
	}
}
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] + dist[u][depth[x]]);
	}
	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;
}

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