Submission #127918

#	Time	Username	Problem	Language	Result	Execution time	Memory
127918		Just_Solve_The_Problem	Factories (JOI14_factories)	C++11	15 / 100	6451 ms	232832 KiB

factories

#include "factories.h"
// #include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = (int)5e5 + 7;

struct fen {
	int tree[maxn];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val) {
		while(pos < maxn) {
			tree[pos] += val;
			pos = pos | pos + 1;
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & r + 1) - 1;
		}
		return res;
	}
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};
fen tr1, tr2;

int tiktak;
int tin[maxn], tout[maxn];
int lc[20][maxn];
int asd[5005][5005];
ll h[maxn];
vector<pair<int, int>> gr[maxn];

void dfs(int v, int pr) {
	tin[v] = ++tiktak;
	lc[0][v] = pr;
	for (int i = 1; i < 20; i++) {
		lc[i][v] = lc[i - 1][lc[i - 1][v]];
	}
	for (auto id : gr[v]) {
		int to = id.first;
		int w = id.second;
		if (to == pr) continue;
		h[to] = h[v] + w;
		dfs(to, v);
	}
	tout[v] = tiktak;
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;
	for (int i = 19; i >= 0; i--) {
		if (!upper(lc[i][a], b)) a = lc[i][a];
	}
	return lc[0][a];
}

ll dist(int a, int b) {
	return h[a] + h[b] - 2 * h[asd[a][b]];
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N - 1; i++) {
		gr[A[i]].push_back({B[i], D[i]});
		gr[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, 0);
	for (int i = 0; i < N; i++) {
		asd[i][i] = i;
		for (int j = i + 1; j < N; j++) {
			asd[i][j] = asd[j][i] = lca(i, j);
		}
	}
}

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

Compilation message (stderr)

factories.cpp: In member function 'void fen::upd(int, int)':
factories.cpp:19:20: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
    pos = pos | pos + 1;
                ~~~~^~~
factories.cpp: In member function 'int fen::get(int)':
factories.cpp:26:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
    r = (r & r + 1) - 1;
             ~~^~~

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