Submission #128096

#	Time	Username	Problem	Language	Result	Execution time	Memory
128096		Just_Solve_The_Problem	Factories (JOI14_factories)	C++11	100 / 100	2616 ms	272868 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) {
	tin[v] = ++tiktak;
	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);
	}
	tout[v] = tiktak;
}

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];
vector <int> vec;
int st;

void dfs1(int v, int pr, ll &ans) {
	dp1[v] = dp2[v] = 1e18;
	if (col[v] == 1) dp1[v] = 0;
	if (col[v] == 2) dp2[v] = 0;
	col[v] = 0;
	while (st < vec.size() && tin[vec[st]] <= tout[v]) {
		int to = vec[st]; st++;
		dfs1(to, v, ans);
		dp1[v] = min(dp1[v], dp1[to] + h[to] - h[v]);
		dp2[v] = min(dp2[v], dp2[to] + h[to] - h[v]);
	}
	ans = min(ans, dp1[v] + dp2[v]);
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans = 1e18;
  for (int i = 0; i < S; i++) {
		vec.push_back(X[i]);
		col[X[i]] = 1;
  }
  for (int i = 0; i < T; i++) {
		vec.push_back(Y[i]);
		col[Y[i]] = 2;
  }
  sort(vec.begin(), vec.end(), [&](const int &A, const int &B) {
		return tin[A] < tin[B];
  });
  for (int i = vec.size() - 2; i >= 0; i--) {
		vec.push_back(lca(vec[i], vec[i + 1]));
  }
  sort(vec.begin(), vec.end(), [&](const int &A, const int &B) {
		return tin[A] < tin[B];
  });
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  st = 1;
  dfs1(vec[0], vec[0], ans);
  vec.clear();
	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)]);
                                                                    ~~^~~
factories.cpp: In function 'void dfs1(int, int, long long int&)':
factories.cpp:88:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (st < vec.size() && tin[vec[st]] <= tout[v]) {
         ~~~^~~~~~~~~~~~

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