Submission #28895

#	Time	Username	Problem	Language	Result	Execution time	Memory
28895		cdemirer	Factories (JOI14_factories)	C++14	0 / 100	6000 ms	199568 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int _N;
vector<vector<ii> > edges;
int parent[500000][20];
int depth[500000];
ll rootdist[500000];
int twopow[20];
int pff[524289];
int lcadp[5000][5000];

void dfs(int x, int d, ll dst) {
	depth[x] = d;
	rootdist[x] = dst;
	for (int i = 0; i < edges[x].size(); i++) {
		if (edges[x][i].first == parent[x][0]) continue;
		parent[edges[x][i].first][0] = x;
		dfs(edges[x][i].first, d+1, dst + edges[x][i].second);
	}
}
void prt(int x, int e) {
	if (depth[x] >= twopow[e]) {
		int q = parent[x][e-1];
		parent[x][e] = parent[q][e-1];
	}
	for (int i = 0; i < edges[x].size(); i++) {
		if (edges[x][i].first == parent[x][0]) continue;
		prt(edges[x][i].first, e);
	}
}
int lca(int a, int b) {
	if (lcadp[a][b] != -1) return lcadp[a][b];
	int _a = a, _b = b;
	if (depth[a] > depth[b]) {
		int t = a;
		a = b;
		b = t;
	}
	int dif = depth[b] - depth[a];
	int c = 0;
	while (dif) {
		if (dif & 1) {
			b = parent[b][c];
		}
		c++;
		dif >>= 1;
	}
	/*while (depth[b] > depth[a]) {
		int dif = depth[b] - depth[a];
		//cerr << b << endl;
		dif = dif & -dif;
		int c = pff[dif];
		b = parent[b][c];
	}*/
	int d = depth[a];
	for (int x = 19; x >= 0; x--) {
		int q = twopow[x];
		if (q > d) continue;
		if (parent[a][x] != parent[b][x]) {
			a = parent[a][x];
			b = parent[b][x];
		}
	}
	int ans = a;
	if (a != b) ans = parent[a][0];
	//cerr << a << " " << b << " " << ans << endl;
	lcadp[_a][_b] = lcadp[_b][_a] = ans;
	return ans;
}
ll dst(int a, int b) {
	int c = lca(a, b);
	return rootdist[a] + rootdist[b] - 2 * rootdist[c];
}

void Init(int N, int A[], int B[], int D[]) {
	memset(lcadp, -1, sizeof(lcadp));
	_N = N;
	edges.resize(N);
	for (int i = 0; i < N; i++) {
		edges[A[i]].pb(mp(B[i], D[i]));
		edges[B[i]].pb(mp(A[i], D[i]));
	}
	parent[0][0] = -1;
	dfs(0, 0, 0);
	twopow[0] = 1;
	//pff[1] = 0;
	for (int i = 1; i < 20; i++) {
		twopow[i] = (int) pow(2, i);
		//pff[twopow[i]] = i;
		prt(0, i);
	}
}

long long Query(int S, int X[], int T, int Y[]) {

	ll best = (ll)1e18;
	for (int i = 0; i < S; i++) {
		for (int j = 0; j < T; j++) {
			best = min(best, dst(X[i], Y[j]));
		}
	}
	return best;

}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, ll)':
factories.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                    ^
factories.cpp: In function 'void prt(int, int)':
factories.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                    ^

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