Submission #1156744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156744		nguyn	Factories (JOI14_factories)	C++20	100 / 100	1549 ms	294572 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
#define pil pair<int, ll>

const int MN = 1e6 + 5;
const ll inf = 1e18;

int n, q, tin[MN], tout[MN], h[MN], timedfs, type[MN];
ll f[MN][2], res, s[MN];
pii rmq[21][MN];
vector<pil> g[MN];
vector<pil> g2[MN];


void pre_dfs(int u, int p) {
	tin[u] = ++timedfs;
	rmq[0][timedfs] = {h[u], u};
	for (auto it : g[u]) {
		int v = it.F;
		int w = it.S;
		if (v == p) continue;
		h[v] = h[u] + 1;
		s[v] = s[u] + w;
		pre_dfs(v, u);
		rmq[0][++timedfs] = {h[u], u};
	}
	tout[u] = timedfs;
	rmq[0][timedfs] = {h[u], u};
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		A[i]++, B[i]++;
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	for (int i = 1; i <= n; i++) type[i] = -1;
	pre_dfs(1, 0);
	for (int i = 1; i < 21; i++) {
		for (int j = 1; j <= timedfs - (1 << i) + 1; j++) {
			rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
		}
	}
}

bool in(int u, int v) {
	return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

int lca(int u, int v) {
	int l = tin[u];
	int r = tin[v];
	if (l > r) swap(l, r);
	int lg = __lg(r - l + 1);
//    assert(l <= r);
	return min(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]).S;
}

bool cmp(int u, int v) {
	return tin[u] < tin[v];
}

void dfs(int u) {
    f[u][0] = f[u][1] = inf;
    if (type[u] != -1) {
        f[u][type[u]] = 0;
    }
    for (auto it : g2[u]) {
        int v = it.F;
        ll w = it.S;
        dfs(v);
        res = min({res, f[u][0] + w + f[v][1], f[u][1] + w + f[v][0]});
        f[u][0] = min(f[u][0], f[v][0] + w);
        f[u][1] = min(f[u][1], f[v][1] + w);
    }
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> cur;
	for (int i = 0; i < S; i++) {
		cur.pb(X[i] + 1);
		type[X[i] + 1] = 0;
	}
	for (int i = 0; i < T; i++) {
		cur.pb(Y[i] + 1);
		type[Y[i] + 1] = 1;
	}
    sort(cur.begin(), cur.end(), cmp);
    int sz = cur.size() - 1;
    for (int i = 0; i < sz; i++) {
//        int l = lca(cur[i], cur[i + 1]);
//        cout << cur[i] << ' ' << cur[i + 1] << ' ' << l << endl;
        cur.pb(lca(cur[i], cur[i + 1]));
    }
    sort(cur.begin(), cur.end(), cmp);
    cur.erase(unique(cur.begin(), cur.end()), cur.end());
    stack<int> st;
    for (int u : cur) {
        while(!st.empty() && !in(st.top(), u)) {
            st.pop();
        }
        if (!st.empty()) {
            g2[st.top()].pb({u, s[u] - s[st.top()]});
//            cout << st.top() << ' ' << u << ' ' << s[u] - s[st.top()] << endl;
        }
        st.push(u);
    }
    res = inf;
    dfs(cur[0]);
    for (int u : cur) {
        g2[u].clear();
        type[u] = -1;
    }
    return res;
}

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