Submission #359291

#	Time	Username	Problem	Language	Result	Execution time	Memory
359291		pure_mem	Factories (JOI14_factories)	C++14	100 / 100	7708 ms	199508 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int N = 5e5 + 2;
const ll INF = 1e18;

int lg[N * 4];
int n, sz[N], mx[N], block[N], cent_pr[N], depth[N], ord[21][N * 4], timer, tin[N];
ll dp[N], mcost[N];
int last_used[N], Q;
vector< pair< int, int > > g[N];

void dfs_sz(int v, int pr){
	sz[v] = 1, mx[v] = 0;
	for(pair<int, int> to: g[v]){
		if(to.X == pr || block[to.X])
			continue;
		dfs_sz(to.X, v), sz[v] += sz[to.X];
		mx[v] = (sz[mx[v]] < sz[to.X] ? to.X: mx[v]);
	}
}

int get_cent(int v){
	int u = v;
	while(sz[mx[u]] * 2 > sz[v])
		u = mx[u];
	return u;
}

void cent(int v, int pr){
	dfs_sz(v, v), v = get_cent(v);
	cent_pr[v] = pr, block[v] = 1;
	for(pair<int, int> to: g[v]){
		if(!block[to.X])
			cent(to.X, v);
	}
}

void dfs_prep(int v, int pr){
	tin[v] = ++timer, ord[0][timer] = v;
	for(pair<int, int> to: g[v]){
		if(to.X == pr)
			continue;
		dp[to.X] = dp[v] + to.Y, depth[to.X] = depth[v] + 1;
		dfs_prep(to.X, v);
		ord[0][++timer] = v;
	}	
}

ll calc(int x, int y){
	if(tin[x] > tin[y])
		swap(x, y);
	int mid = (tin[y] - tin[x] + 1);
	mid = (depth[ord[lg[mid]][tin[x]]] < depth[ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]] ? ord[lg[mid]][tin[x]]: ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]);
//	cerr << x - 1 << " " << y - 1 << " " << mid - 1 << "\n";
	return dp[x] + dp[y] - 2 * dp[mid];
}

void Init(int N2, int A[], int B[], int D[]) {
	for(int i = 2;i < N * 4;i++)
		lg[i] = lg[i / 2] + 1;
	n = N2;
	for(int i = 0;i < n - 1;i++){
		g[A[i] + 1].push_back(MP(B[i] + 1, D[i]));
		g[B[i] + 1].push_back(MP(A[i] + 1, D[i]));
	}
	cent(1, 0);
	dfs_prep(1, 1);
	for(int i = 1;i <= 20;i++)
		for(int j = 1;j + (1 << i) - 1 <= timer;j++)
			ord[i][j] = (depth[ord[i - 1][j]] < depth[ord[i - 1][j + (1 << (i - 1))]] ? ord[i - 1][j]: ord[i - 1][j + (1 << (i - 1))]);
}

long long Query(int S, int X[], int T, int Y[]) {
//	cerr << "NEXT\n";
	ll ans = INF;
 	Q++;
 	for(int i = 0;i < S;i++){
		X[i]++;
		int j = X[i];
		while(j){
			if(last_used[j] != Q)
				last_used[j] = Q, mcost[j] = INF;
			mcost[j] = min(mcost[j], calc(j, X[i]));
		//	cerr << j - 1 << " " << X[i - 1] << " " << calc(j, X[i]) << "\n";
			j = cent_pr[j];
		}
  	}
  	for(int i = 0;i < T;i++){
  		Y[i]++;
  		int j = Y[i];
  		while(j){
  			if(last_used[j] != Q)
  				last_used[j] = Q, mcost[j] = INF;
  			ans = min(ans, mcost[j] + calc(j, Y[i]));
  		//	cerr << j - 1 << " " << Y[i] - 1 << " " << ans << " " << mcost[j] << " " << calc(j, Y[i]) << "\n";
  			j = cent_pr[j];
  		}
  	}
	return ans;
}

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