Submission #573207

#	Time	Username	Problem	Language	Result	Execution time	Memory
573207		Arnch	Factories (JOI14_factories)	C++17	100 / 100	3359 ms	219844 KiB

factories

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

using namespace std;

typedef long long ll;

//#define Sz(x) int((x).size())
//#define All(x) (x).begin(), (x).end()
//#define wtf(x) cout<<#x <<" : " <<x <<endl

const ll inf = 1e18, maxn = 1e6 + 10, Log = 25;

int n, par[maxn][Log], st[maxn], fn[maxn], h[maxn], cnt[maxn], tim;
ll d[maxn], dp[maxn][2], ans;
vector<pair<int, ll> > G[maxn], child[maxn];

bool cmp(int i, int j) {
	return st[i] < st[j];
}
void dfs(int x, int p = 0) {
	st[x] = tim++;
	par[x][0] = p;
	for(int i = 1; i < Log; i++) par[x][i] = par[par[x][i - 1]][i - 1];
	for(auto i : G[x]) {
		if(i.first == p) continue;
		h[i.first] = h[x] + 1, d[i.first] = d[x] + i.second;
		dfs(i.first, x);
	}
	fn[x] = tim++;
}
int get_par(int x, int y) {
	for(int i = 0; i < Log; i++) {
		if((y >> i) & 1) x = par[x][i];
	}
	return x;
}
int lca(int x, int y) {
	if(h[x] > h[y]) swap(x, y);
	y = get_par(y, h[y] - h[x]);
	if(x == y) return x;
	for(int i = Log - 1; i >= 0; i--) {
		if(par[x][i] != par[y][i]) {
			x = par[x][i], y = par[y][i];
		}
	}
	return par[x][0];
}
void main_dfs(int x) {
	dp[x][0] = dp[x][1] = inf;
	if(cnt[x] == 0) dp[x][0] = 0;
	if(cnt[x] == 1) dp[x][1] = 0;
	for(auto i : child[x]) {
		main_dfs(i.first);
		dp[x][0] = min(dp[x][0], dp[i.first][0] + i.second);
		dp[x][1] = min(dp[x][1], dp[i.first][1] + i.second);
	}
	ans = min(ans, dp[x][0] + dp[x][1]);
}
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		G[A[i]].push_back({B[i], D[i]});
		G[B[i]].push_back({A[i], D[i]});
	}
	dfs(0);
	for(int i = 0; i < n; i++) cnt[i] = -1;
}
long long Query(int S, int X[], int T, int Y[]) {
	vector<int> vc;
	for(int i = 0; i < S; i++) vc.push_back(X[i]), cnt[X[i]] = 0;
	for(int i = 0; i < T; i++) vc.push_back(Y[i]), cnt[Y[i]] = 1;
	sort(vc.begin(), vc.end(), cmp);
	int sz = vc.size();
	for(int i = 0; i < sz - 1; i++) {
		vc.push_back(lca(vc[i], vc[i + 1]));
	}
	sort(vc.begin(), vc.end(), cmp);
	vc.erase(unique(vc.begin(), vc.end()), vc.end());
	stack<int> st;
	st.push(vc[0]);
	for(int i = 1; i < vc.size(); i++) {
		int v = vc[i];
		while(fn[st.top()] < fn[v]) st.pop();
		child[st.top()].push_back({v, d[v] - d[st.top()]});
		st.push(v);
	}
	ans = inf;
	main_dfs(vc[0]);
	for(auto i : vc) {
		child[i].clear();
		cnt[i] = -1;
		dp[i][0] = dp[i][1] = inf;
	}
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i = 1; i < vc.size(); i++) {
      |                 ~~^~~~~~~~~~~

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