Submission #585947

#	Time	Username	Problem	Language	Result	Execution time	Memory
585947		M_W	Factories (JOI14_factories)	C++17	100 / 100	4682 ms	186712 KiB

factories

#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int sz[500005], lvl[500005], pa[500005];
bool blocked[500005];
vector<ii> adj[500005];
long long dist[21][500005];

// Centroid

void dfs(int a, int p){
	sz[a] = 1;
	for(auto [x, w]: adj[a]){
		if(blocked[x] || x == p) continue;
		dfs(x, a);
		sz[a] += sz[x];
	}
}

void dfs_dis(int a, int p, int lv){
	for(auto [x, w] : adj[a]){
		if(x == p || blocked[x]) continue;
		dist[lv][x] = dist[lv][a] + w;
		dfs_dis(x, a, lv);
	}
}

void dec(int a, int p){
	dfs(a, a);
	int cur = a, prev = -1;
	while(true){
		int mx = -1, ch;
		for(auto [x, w] : adj[cur]){
			if(blocked[x] || x == prev) continue;
			if(sz[x] > mx){
				mx = sz[x];
				ch = x;
			}
		}
		if(mx * 2 > sz[a]){
			prev = cur;
			cur = ch;
		}
		else break;
	}
	lvl[cur] = p == -1 ? 0 : lvl[p] + 1;
	dfs_dis(cur, cur, lvl[cur]);
	blocked[cur] = true;
	
	pa[cur] = p;
	for(auto [x, w] : adj[cur]) if(!blocked[x]) dec(x, cur);
}

long long val[500005];

void Init(int N, int A[], int B[], int D[]){
	for(int i = 0; i < N - 1; i++){
		adj[A[i]].push_back({B[i], D[i] * 1ll});
		adj[B[i]].push_back({A[i], D[i] * 1ll});
	}
	dec(0, -1);
	for(int i = 0; i < N; i++) val[i] = 1e15;
}

void upd(int u){
	int old_u = u;
	for(; u != -1; u = pa[u]){
		val[u] = min(val[u], dist[lvl[u]][old_u]);
	}
}

long long query(int u){
	long long res = 1e15;
	int old_u = u;
	for(; u != -1; u = pa[u]){
		res = min(res, val[u] + dist[lvl[u]][old_u]);
	}
	return res;
}

void reset(int u){
	for(; u != -1; u = pa[u]) val[u] = 1e15;
}

long long Query(int S, int X[], int T, int Y[]) {
	long long res = 1e15;
	for(int i = 0; i < S; i++) upd(X[i]);
	for(int i = 0; i < T; i++) res = min(res, query(Y[i]));
	for(int i = 0; i < S; i++) reset(X[i]);
	
	return res;
}

Compilation message (stderr)

factories.cpp: In function 'void dec(int, int)':
factories.cpp:51:49: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |  for(auto [x, w] : adj[cur]) if(!blocked[x]) dec(x, cur);
      |                                              ~~~^~~~~~~~

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