제출 #1151162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151162		mingga	Factories (JOI14_factories)	C++20	0 / 100	5452 ms	348252 KiB

factories

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

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 1e6 + 7;
vector<pair<int, ll>> g[N], sg[N];


int h[N];
ll lev[N];
int in[N], lg[N], out[N];
pair<int, int> rmq[N * 2][25];
int label[N];
ll dp[N][2], f[N];
int timer = 0;

void dfs(int u, int p) {
	in[u] = ++timer;
	cerr << "TURN " << u << ' ' << lev[u] << ' ' << h[u] << ln;
	rmq[timer][0] = {h[u], u};
	for(auto x : g[u]) {
		int v = x.fi;
		ll w = x.se;
		if(v == p) continue;
		h[v] = h[u] + 1;
		cerr << u << "TO " << v << " " << w << ln;
		lev[v] = lev[u] + w;
		dfs(v, u);
		rmq[++timer][0] = {h[u], u};
	}
	out[u] = timer;
}

int lca(int u, int v) {
	int l = in[u], r = in[v];
	// cerr << u << ' ' << v << ' ' << l << ' ' << r << ln;
	if(l > r) swap(l, r);
	int k = lg[r - l + 1];
	return min(rmq[l][k], rmq[r - (1 << k) + 1][k]).se;
}

ll dist(int u, int v) {
	return lev[u] + lev[v] - 2 * lev[lca(u, v)];
}

bool inside(int x, int y) {
	return in[x] <= in[y] and out[x] >= out[y];
}

void Init(int n, int a[], int b[], int d[]) {
	timer = 0;
	for(int i = 0; i < n - 1; i++) {
		int u = a[i] + 1, v = b[i] + 1;
		g[u].pb({v, d[i]});
		g[v].pb({u, d[i]});
	}
	dfs(1, 0);
	// for(int i = 1; i <= n; i++) cerr << i << ' ' << lev[i] << ln; 
	for(int i = 2; i <= timer; i++) lg[i] = lg[i / 2] + 1;
	for(int j = 1; (1 << j) <= timer; j++) {
		for(int i = 1; i + (1 << j) <= timer; i++) {
			rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
}

void dfs_calc(int u, int p) {
	dp[u][0] = dp[u][1] = 2e18;
	if(label[u] > 0) dp[u][label[u] - 1] = 0;
	f[u] = 2e18;
	for(auto x: sg[u]) {
		int v = x.fi;
		ll w = x.se;
		if(v == p) continue;
		dfs_calc(v, u);
		f[u] = min({f[u], dp[u][0] + dp[v][1] + w, dp[u][1] + dp[v][0] + w});
		dp[u][0] = min(dp[u][0], dp[v][0] + w);
		dp[u][1] = min(dp[u][1], dp[v][1] + w);
	}
}

ll Query(int s, int x[], int t, int y[]) {
	vector<int> vec;
	for(int i = 0; i < s; i++) {
		x[i]++;
		label[x[i]] = 1;
		vec.pb(x[i]);
	}
	for(int i = 0; i < t; i++) {
		y[i]++;
		label[y[i]] = 2;
		vec.pb(y[i]);
	}
	sort(all(vec), [&](const int x, const int y) {
		return in[x] < in[y];
	});
	int m = sz(vec);
	for(int i = 1; i < m; i++) {
		vec.pb(lca(vec[i], vec[i - 1]));
	}
	sort(all(vec), [&](const int x, const int y) {
		return in[x] < in[y];
	});
	vec.erase(unique(all(vec)), vec.end());
	stack<int> st;
	for(int x : vec) {
		while(sz(st) and !inside(st.top(), x)) st.pop();
		if(sz(st)) {
			ll w = dist(x, st.top());
			sg[st.top()].pb({x, w});
			sg[x].pb({st.top(), w});
		}
		st.push(x);
	}
	dfs_calc(vec[0], 0);
	ll ans = inf;
	for(int x : vec) ans = min(ans, f[x]);
	for(int x : vec) sg[x].clear(), label[x] = dp[x][0] = dp[x][1] = f[x] = 0;
	return ans;
}


//TESTING
// int A[N], B[N], D[N];
// int X[N], Y[N];

// signed main() {
// 	cin.tie(0) -> sync_with_stdio(0);
// 	int n, q; cin >> n >> q;
// 	for(int i = 0; i < n - 1; i++) {
// 		int u, v, w; cin >> u >> v >> w;
// 		A[i] = u, B[i] = v, D[i] = w;
// 	}
// 	Init(n, A, B, D);
// 	for(int i = 1; i <= q; i++) {
// 		int s, t; cin >> s >> t;
// 		for(int i = 0; i < s; i++) {
// 			cin >> X[i];
// 		}
// 		for(int i = 0; i < t; i++) {
// 			cin >> Y[i];
// 		}
// 		cout << Query(s, X, t, Y) << ln;
// 		for(int i = 0; i < s; i++) {
// 			X[i] = 0;
// 		}
// 		for(int i = 0; i < t; i++) {
// 			Y[i] = 0;
// 		}
// 	}
// }

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