제출 #1031816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031816		juicy	공장들 (JOI14_factories)	C++17	100 / 100	1178 ms	211916 KiB

factories

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int mxN = 5e5 + 5, LG = 20;
const long long inf = 1e18;
 
int ord[mxN], spt[LG][2 * mxN], lg[2 * mxN], tout[mxN];
long long dep[mxN], dp[mxN][2];
bool vs[mxN];
vector<pair<int, int>> g[mxN];
vector<int> graph[mxN];

int timer = 0;
 
void pre_dfs(int u) {
	spt[0][ord[u] = ++timer] = u;
	for (auto [v, w] : g[u]) {
		if (!ord[v]) {
			dep[v] = dep[u] + w;
			pre_dfs(v);
			spt[0][++timer] = u;
		}
	}
	tout[u] = timer;
}
 
int mint(int u, int v) {
	return ord[u] < ord[v] ? u : v;
}
 
int lca(int u, int v) {
	int l = ord[u], r = ord[v];
	if (l > r) {
		swap(l, r);
	}
	int k = lg[r - l + 1];
	return mint(spt[k][l], spt[k][r - (1 << k) + 1]);
}
 
long long dis(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void Init(int N, int *A, int *B, int *D) {
	for (int i = 0; i < N - 1; ++i) {
    	++A[i], ++B[i];
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	pre_dfs(1);
	for (int i = 2; i <= timer; ++i) {
		lg[i] = lg[i / 2] + 1;
	}
	for (int j = 1; j < LG; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
			spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
		}
	}
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < 2; ++j) {
      dp[i][j] = inf;
    }
  }
}
 
long long Query(int S, int *X, int T, int *Y) {
	vector<int> ver;
	auto add = [&](int u) {
		if (!vs[u]) {
			ver.push_back(u);
			vs[u] = 1;
		}
	};
	for (int i = 0; i < T; ++i) {
		add(++Y[i]);
		dp[Y[i]][0] = dep[Y[i]];
	}
	for (int i = 0; i < S; ++i) {
		add(++X[i]);
		dp[X[i]][1] = dep[X[i]];
	}
	sort(ver.begin(), ver.end(), [&](int i, int j) {
		return ord[i] < ord[j];
	});
	int m = ver.size();
	for (int i = 1; i < m; ++i) {
		add(lca(ver[i], ver[i - 1]));
	}
	sort(ver.begin(), ver.end(), [&](int i, int j) {
		return ord[i] < ord[j];
	});
	vector<int> st;
	for (int u : ver) {
		while (st.size() && tout[st.back()] < ord[u]) {
			st.pop_back();
		}
		if (st.size()) {
			int p = st.back();
			graph[p].push_back(u);
		}
		st.push_back(u);
	}
	long long ans = inf;
	for (int i = ver.size() - 1; ~i; --i) {
		int u = ver[i];
		for (int v : graph[u]) {
			for (int j = 0; j < 2; ++j) {
				dp[u][j] = min(dp[u][j], dp[v][j]);
			}
		}
		ans = min(ans, dp[u][0] + dp[u][1] - 2 * dep[u]);
	}
	for (int u : ver) {
		vs[u] = 0;
    graph[u].clear();
    for (int j = 0; j < 2; ++j) {
      dp[u][j] = inf;
    }
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:63:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |    spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~

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