Submission #76738

#	Time	Username	Problem	Language	Result	Execution time	Memory
76738		shoemakerjo	Factories (JOI14_factories)	C++14	15 / 100	8032 ms	274816 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pil pair<int, ll>
 
#define maxn 500010
int n;
vector<vector<int>> adj(maxn);
vector<vector<ll>> adjd(maxn);
 
//run a centroid decomposition
 
 
int subsize[maxn];
bool marked[maxn];
ll dr[19][maxn]; 
ll mycomp[19][maxn]; //which component i am in (specify by centroid is good)
ll curdist[maxn];
int cp[maxn];
 
ll inf = 1LL << 60;
ll curmin[maxn]; //for the queries
int cl;
int cc;
 
void dfs(int u, int p, bool op = false) {
 
	cp[u] = p;
	subsize[u] = 1;
	if (op) {
		// cout << u << " is in " << cc << " at level " << cl << endl;
		dr[cl][u] = curdist[u];
		mycomp[cl][u] = cc;
	}
	for (int i = 0; i < adj[u].size(); i++)  {
		int nx = adj[u][i];
		if (nx == p || marked[nx]) continue;
		curdist[nx] = curdist[u] + adjd[u][i];
 
		dfs(nx, u, op);
		subsize[u] += subsize[nx];
	}
}
 
int getcentroid(int u, int csize) {
	curdist[u] = 0LL;
	dfs(u, -1);
	int cur = u;
	bool fin = false;
	while (!fin) {
		fin = true;
		for (int nx : adj[cur]) {
			if (marked[nx] || nx == cp[cur]) continue;
			if (subsize[nx] > csize/2) {
				fin = false;
				cur = nx;
				break;
			}
		}	
	}
	return cur;
 
}
 
void go(int u, int csize, int level) {
	int cen = getcentroid(u, csize);
	curdist[cen] = 0LL;
	cc = cen;
	cl = level;
	dfs(cen, -1, true);
	marked[cen] = true;
	for (int cur : adj[cen]) {
		if (!marked[cur])
			go(cur, subsize[cur], level+1);
	}
 
}
 
void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < 19; i++) {
		fill(mycomp[i], mycomp[i]+maxn, -1);
	}
	n = N;
	for (int i = 0; i < N-1; i++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
		adjd[A[i]].push_back(D[i]);
		adjd[B[i]].push_back(D[i]);
	}
	fill(curmin, curmin+maxn, inf);
	go(0, n, 0);
}
 
ll Query(int S, int X[], int T, int Y[]) {
	ll ans = inf;
	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) break;
			curmin[mycomp[j][val]] = 
				min(curmin[mycomp[j][val]], dr[j][val]);
		}
	}
 
	for (int i = 0; i < T; i++) {
		int val = Y[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) break;
 
			ans = min(ans, 
				curmin[mycomp[j][val]] + dr[j][val]);
		}
	}
 
	for (int i = 0; i < S; i++) {
		int val = X[i];
		for (int j = 0; j < 19; j++) {
			if (mycomp[j][val] == -1) break;
			curmin[mycomp[j][val]] = inf;
		}
	}
 
  	return ans;
}
 
//COULD NOT SUBMIT AT TIME FIRST SOLVED
//

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, bool)':
factories.cpp:37:20: 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: 0 / 18
• Subtask 3: 0 / 67