Submission #169670

#	Time	Username	Problem	Language	Result	Execution time	Memory
169670		oolimry	Factories (JOI14_factories)	C++14	100 / 100	5230 ms	347172 KiB

factories

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

typedef pair<long long, long long> ii;
static vector<ii> adj[500005];
static vector<ii> parent[500005];
static long long dis[500005];
static int sz[500005];
static bool cented[500005];

static long long shortest[500005];
 
vector<int> nodes;
void dfs(int u){
	sz[u] = 1;
	nodes.push_back(u);
	for(ii v : adj[u]){
		if(sz[v.first] == 0 && !cented[v.first]){
			dis[v.first] = dis[u] + v.second;
			dfs(v.first);
			sz[u] += sz[v.first];
		}
	}
}

void recurse(int r, int p){
	nodes.clear();
	dfs(r);
	
	int centroid;
	for(int u : nodes){
		int big = sz[r] - sz[u];
		for(ii v : adj[u]){
			if(!cented[v.first] && sz[v.first] < sz[u]){
				big = max(big, sz[v.first]);
			}
		}
		if(2*big <= sz[r]){
			centroid = u;
			break;
		} 
	}

	for(int u : nodes){
		sz[u] = 0;
		if(p != -1) parent[u].push_back(ii(p,dis[u]));
		dis[u] = 0;
	}
	cented[centroid] = true;
	for(ii v : adj[centroid]){
		dis[v.first] = v.second;
		if(!cented[v.first]) recurse(v.first, centroid);
	}
}

const long long inf = 12381293928390122LL;
void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0;i < N-1;i++){
		int u = A[i];
		int v = B[i];
		int w = D[i];
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
	}
	recurse(0,-1);
	for(int i = 0;i < N;i++){
		reverse(parent[i].begin(),parent[i].end());
	}
	fill(shortest,shortest+N,inf);
}

long long Query(int S, int X[], int T, int Y[]) {
	
	long long ans = inf;
	for(int i = 0;i < S;i++){
		int u = X[i];
		shortest[u] = 0;
		for(ii v : parent[u]){
			shortest[v.first] = min(shortest[v.first],v.second);
		}
	}
	
	for(int i = 0;i < T;i++){
		int u = Y[i];
		ans = min(ans, shortest[u]);
		for(ii v : parent[u]){
			ans = min(ans, shortest[v.first] + v.second);
		}
	}
	
	for(int i = 0;i < S;i++){
		int u = X[i];
		shortest[u] = inf;
		for(ii v : parent[u]){
			shortest[v.first] = inf;
		}
	}
	
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void recurse(int, int)':
factories.cpp:31:6: warning: 'centroid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int centroid;
      ^~~~~~~~

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