Submission #422675

#	Time	Username	Problem	Language	Result	Execution time	Memory
422675		amunduzbaev	Factories (JOI14_factories)	C++14	100 / 100	4930 ms	253012 KiB

factories

#include "factories.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define int long long
#define sz(x) (int)x.size()
#define i32 int32_t

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int MAXN = 5e5+5;
const int mod = 1e9+7;
const int inf = 1e18;

vector<pii> edges[MAXN];
int ver[MAXN][20], cen[MAXN][20], cc, sz[MAXN];
int used[MAXN], d[MAXN], n;

void dfs(int u, int p, int j, int d = 0){
	ver[u][j] = d, cen[u][j] = cc, sz[u] = 1;
	for(auto x : edges[u]){
		if(used[x.ff] || p == x.ff) continue;
		dfs(x.ff, u, j, d+x.ss), sz[u] += sz[x.ff];
	}
}

int centr(int u, int p = -1){
	for(auto x : edges[u]){
		if(x.ff == p || used[x.ff]) continue;
		if(sz[x.ff] > n / 2) return centr(x.ff, u);
	} return u;
}

void cdec(int u, int j = 0){
	dfs(u, -1, j), n = sz[u];
	cc = centr(u);
	//~ cout<<cc<<"\n";
	
	dfs(cc, -1, j);
	used[cc] = 1;
	
	for(auto x : edges[cc]){
		if(used[x.ff]) continue;
		cdec(x.ff, j+1);
	}
}

void Init(i32 N, i32 a[], i32 b[], i32 D[]) {
	n = N;
	for(int i=0;i<n-1;i++){ a[i]++, b[i]++;
		edges[a[i]].pb({b[i], D[i]}), edges[b[i]].pb({a[i], D[i]}); 
	} 
	
	cdec(1);
	n = N;
	for(int i=1;i<=N;i++) d[i] = inf;
}

int Query(i32 s, i32 x[], i32 t, i32 y[]) {
	for(int i=0;i<s;i++) x[i]++;
	for(int i=0;i<t;i++) y[i]++;
	int res = inf;
		
	for(int i=0;i<s;i++)
		for(int j=0;j<20;j++) if(cen[x[i]][j]) umin(d[cen[x[i]][j]], ver[x[i]][j]);

	for(int i=0;i<t;i++)
		for(int j=0;j<20;j++) if(cen[y[i]][j]) umin(res, d[cen[y[i]][j]] + ver[y[i]][j]);
	for(int i=0;i<s;i++)
		for(int j=0;j<20;j++) if(cen[x[i]][j]) d[cen[x[i]][j]] = inf;
	return res;
}

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