제출 #117173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117173		Just_Solve_The_Problem	공장들 (JOI14_factories)	C++11	0 / 100	24 ms	12800 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];

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[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);
}

long long Query(int S, int X[], int T, int Y[]) {
  vector<pair<int, int>> v;
  int cur[2];
  cur[0] = cur[1] = 0;
  sort(X, X + S, [&](const int &A, const int &B) {
		return h[A] < h[B];
  });
  sort(Y, Y + T, [&](const int &A, const int &B) {
		return h[A] < h[B];
  });
  while (cur[0] < S && cur[1] < T) {
		if (h[X[cur[0]]] < h[Y[cur[1]]]) {
			v.push_back({X[cur[0]], 0});
			cur[0]++;
		} else {
			v.push_back({Y[cur[1]], 1});
			cur[1]++;
		}
  }
  while (cur[0] < S) {
		v.push_back({X[cur[0]], 0});
		cur[0]++;
  }
  while (cur[1] < T) {
		v.push_back({Y[cur[1]], 1});
		cur[1]++;
  }
  ll ans = 1e18;
  int lst1, lst2;
  lst1 = lst2 = -1;
  for (auto id : v) {
		int sec = id.second;
		int V = id.first;
		if (!sec) {
			if (lst2 != -1) {
				ans = min(ans, dist(lst2, V));
			}  
			lst1 = V;
		} else {
			if (lst1 != -1) {
				ans = min(ans, dist(lst1, V));
			}
			lst2 = V;
		}
  }
	return ans;
}

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