Submission #56997

#	Time	Username	Problem	Language	Result	Execution time	Memory
56997		RezwanArefin01	Factories (JOI14_factories)	C++17	100 / 100	7537 ms	247096 KiB

factories

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

typedef long long ll; 

const int MAX = 5e5 + 10; 
vector<int> adj[MAX], cost[MAX]; 
int lvl[MAX], sub[MAX], p[MAX], vis[MAX];
ll d[20][MAX], ans[MAX];
	
void calc(int u, int par) { sub[u] = 1; 
	for(int v : adj[u]) if(v - par && !vis[v]) 
		calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
	for(int v : adj[u]) if(v - par && !vis[v]) 
		if(sub[v] > r) return centroid(v, u, r);
	return u;
}
void dfs(int l, int u, int par, int pcost) {
	if(par + 1) d[l][u] = d[l][par] + pcost; 
	for(int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i], c = cost[u][i]; 
		if(v == par || vis[v]) continue; 
		dfs(l, v, u, c); 
	}
}
void decompose(int u, int par) {
	calc(u, -1);
	int c = centroid(u, -1, sub[u] >> 1);
	vis[c] = 1, p[c] = par; 
	if(par + 1) lvl[c] = lvl[par] + 1;
	dfs(lvl[c], c, -1, 0);
	for(int v : adj[c]) if(v - par && !vis[v]) 
		decompose(v, c);
}

void update(int u) {
	for(int v = u; v + 1; v = p[v]) 
		ans[v] = min(ans[v], d[lvl[v]][u]);
}
ll query(int u) {
	ll ret = 1e18;
	for(int v = u; v + 1; v = p[v])
		ret = min(ret, ans[v] + d[lvl[v]][u]);
	return ret;
}


void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N - 1; i++) {
		int u = A[i], v = B[i], c = D[i];
		adj[u].push_back(v);
		adj[v].push_back(u); 
		cost[u].push_back(c); 
		cost[v].push_back(c); 
	}
	for(int i = 0; i < N; i++) 
		ans[i] = 1e18; 
	decompose(0, -1); 
}

long long Query(int S, int X[], int T, int Y[]) {
	if(S < T) {
		for(int i = 0; i < S; i++) 
			update(X[i]); 
		ll ret = 1e18; 
		for(int i = 0; i < T; i++) 
			ret = min(ret, query(Y[i])); 
		for(int i = 0; i < S; i++) {
			for(int v = X[i]; v + 1; v = p[v]) 
				ans[v] = 1e18; 
		} return ret;
	} else {
		for(int i = 0; i < T; i++) 
			update(Y[i]); 
		ll ret = 1e18; 
		for(int i = 0; i < S; i++) 
			ret = min(ret, query(X[i])); 
		for(int i = 0; i < T; i++) {
			for(int v = Y[i]; v + 1; v = p[v]) 
				ans[v] = 1e18; 
		} return ret;
	} 
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~

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