Submission #128084

#	Time	Username	Problem	Language	Result	Execution time	Memory
128084		Just_Solve_The_Problem	Factories (JOI14_factories)	C++11	33 / 100	8101 ms	252308 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;

int tiktak;
int tin[maxn], tout[maxn];
int lc[20][maxn];
ll h[maxn];
vector<pair<int, int>> gr[maxn];
int numlog[maxn + maxn], pos[maxn], deep[maxn];
vector <int> order;

struct sparse {
	pair<int, int> table[20][maxn + maxn];
	sparse() {} 
	void build() {
		for (int i = 2; i <= order.size(); i++) {
			numlog[i] = numlog[i / 2] + 1;
		}
		for (int i = 0; i <= numlog[order.size()]; i++) {
			for (int j = 0; j < order.size(); j++) {
				if (i == 0) {
					table[i][j] = {deep[order[j]], order[j]};
				} else {
					table[i][j] = min(table[i - 1][j], table[i - 1][min(j + (1 << i - 1), (int)order.size() - 1)]);
				}
			}
		}
	}
	int get(int l, int r) {
		if (l > r) swap(l, r);
		int lg = numlog[r - l + 1];
		return min(table[lg][l], table[lg][r - (1 << lg) + 1]).second;
	}
};
sparse tr;

void dfs(int v, int pr) {
	pos[v] = order.size();
	order.push_back(v);
	for (auto id : gr[v]) {
		int to = id.first;
		int w = id.second;
		if (to == pr) continue;
		h[to] = h[v] + w;
		deep[to] = deep[v] + 1;
		dfs(to, v);
		pos[v] = order.size();
		order.push_back(v);
	}
}

int lca(int a, int b) {
	return tr.get(pos[a], pos[b]);
}

ll dist(int a, int b) {
	return h[a] + h[b] - 2 * h[lca(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);
	tr.build();
}

ll dp1[maxn], dp2[maxn];
int col[maxn];

void dfs1(int v, int pr, ll &ans) {
	dp1[v] = 1e18;
	dp2[v] = 1e18;
	if (col[v] == 1) dp1[v] = 0;
	if (col[v] == 2) dp2[v] = 0;
	for (pair<int, int> id : gr[v]) {
		int to = id.first;
		int w = id.second;
		if (to == pr) continue;
		dfs1(to, v, ans);
		dp1[v] = min(dp1[v], dp1[to] + w);
		dp2[v] = min(dp2[v], dp2[to] + w);
	}
	ans = min(ans, dp1[v] + dp2[v]);
}

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

Compilation message (stderr)

factories.cpp: In member function 'void sparse::build()':
factories.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 2; i <= order.size(); i++) {
                   ~~^~~~~~~~~~~~~~~
factories.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < order.size(); j++) {
                    ~~^~~~~~~~~~~~~~
factories.cpp:31:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
      table[i][j] = min(table[i - 1][j], table[i - 1][min(j + (1 << i - 1), (int)order.size() - 1)]);
                                                                    ~~^~~

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