Submission #169668

#	Time	Username	Problem	Language	Result	Execution time	Memory
169668		oolimry	공장들 (JOI14_factories)	C++14	0 / 100	21 ms	12664 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 int centParent[500005];
static long long disParent[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;
		} 
	}
	
	centParent[centroid] = p;
	disParent[centroid] = dis[centroid];
	
	///reseting
	for(int u : nodes){
		sz[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 = 12381293928390122;
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);
	fill(shortest,shortest+N,inf);
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0;i < S;i++){
		int x = X[i];
		long long d = 0;
		while(x != -1){
			shortest[x] = min(shortest[x],d);
			d += disParent[x];
			x = centParent[x];
		}
	}
	
	long long ans = inf;
	for(int i = 0;i < T;i++){
		int y = Y[i];
		long long d = 0;
		while(y != -1){
			ans = min(ans, shortest[y] + d);
			d += disParent[y];
			y = centParent[y];
		}
	}
	
	
	for(int i = 0;i < S;i++){
		int x = X[i];
		while(x != -1){
			shortest[x] = inf;
			x = centParent[x];
		}
	}
	
	return ans;
}

Compilation message (stderr)

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

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