Submission #684028

#	Time	Username	Problem	Language	Result	Execution time	Memory
684028		nguyentunglam	Factories (JOI14_factories)	C++17	0 / 100	26 ms	24404 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
int st[N], ed[N], h[N], vtx[N << 1], f[21][N << 1], num[N], a[N << 1];
long long d[N], nearest[3][N], res;
int cnt, timer;
bool mark1[N], mark2[N];
vector<pair<int, int> > adj[N];
vector<int> ke[N];
void dfs(int u) {
    st[u] = ++timer;
    vtx[++cnt] = u;
    num[u] = cnt;
    for(auto [v, w] : adj[u]) if (!st[v]) {
        h[v] = h[u] + 1; d[v] = d[u] + w;
        dfs(v);
        vtx[++cnt] = u;
    }
    ed[u] = timer;
}
int lca(int u, int v) {
    int l = num[u], r = num[v];
    if (l > r) swap(l, r);
    int k = log2(r - l + 1);
    int x = f[k][l], y = f[k][r - (1 << k) + 1];
    return h[x] < h[y] ? x : y;
}
void solve(int u) {
    nearest[1][u] = nearest[2][u] = 1e18;
    if (mark1[u]) nearest[1][u] = d[u];
    if (mark2[u]) nearest[2][u] = d[u];
    for(int v : ke[u]) {
        solve(v);
        for(int j = 1; j <= 2; j++) nearest[j][u] = min(nearest[j][u], nearest[j][v]);
    }
    res = min(res, nearest[1][u] + nearest[2][u] - 2LL * d[u]);
}
void Init (int n, int a[], int b[], int d[]) {
    for(int i = 0; i <= n - 2; i++) {
        adj[a[i]].emplace_back(b[i], d[i]);
        adj[b[i]].emplace_back(a[i], d[i]);
    }
    dfs(0);
    for(int i = 1; i <= cnt; i++) f[0][i] = vtx[i];
    for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i + (1 << j) - 1 <= cnt; i++) {
        int x = f[j - 1][i], y = f[j - 1][i + (1 << (j - 1))];
        f[j][i] = h[x] < h[y] ? x : y;
    }
}
long long Query(int s, int x[], int t, int y[]) {
    res = 1e18;
    int k = 0;
    for(int i = 0; i < s; i++) a[++k] = x[i];
    for(int i = 0; i < t; i++) a[++k] = y[i];
    sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
    stack<int> S;
    a[0] = a[k];
    for(int i = 1; i <= k; i++) a[i + k] = lca(a[i], a[i - 1]);
    k <<= 1;
    sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
    S.push(a[1]);
    for(int i = 2; i <= k; i++) if (a[i] != a[i - 1]) {
        while (ed[S.top()] < st[a[i]]) S.pop();
        ke[S.top()].push_back(a[i]);
        S.push(a[i]);
    }
    solve(a[1]);
    for(int i = 1; i <= k; i++) mark1[a[i]] = mark2[a[i]] = 0, ke[a[i]].clear();
    return res;
}
//int main() {
//    #define task ""
//    cin.tie(0) -> sync_with_stdio(0);
//    if (fopen ("task.inp", "r")) {
//        freopen ("task.inp", "r", stdin);
//        freopen ("task.out", "w", stdout);
//    }
//    if (fopen (task".inp", "r")) {
//        freopen (task".inp", "r", stdin);
//        freopen (task".out", "w", stdout);
//    }
//    int n, q; cin >> n >> q;
//    for(int i = 1; i < n; i++) {
//        int u, v, d; cin >> u >> v >> d;
//        adj[u].emplace_back(v, d);
//        adj[v].emplace_back(u, d);
//    }
//    dfs(0);
//    for(int i = 1; i <= cnt; i++) f[0][i] = vtx[i];
//    for(int j = 1; j <= log2(cnt); j++) for(int i = 1; i + (1 << j) - 1 <= cnt; i++) {
//        int x = f[j - 1][i], y = f[j - 1][i + (1 << (j - 1))];
//        f[j][i] = h[x] < h[y] ? x : y;
//    }
//    while (q--) {
//        res = 1e18;
//        int s, t; cin >> s >> t;
//        for(int i = 1; i <= s; i++) cin >> a[i], mark1[a[i]] = 1;
//        for(int i = s + 1; i <= s + t; i++) cin >> a[i], mark2[a[i]] = 2;
//        int k = s + t;
//        sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
//        stack<int> S;
//        a[0] = a[k];
//        for(int i = 1; i <= k; i++) a[i + k] = lca(a[i], a[i - 1]);
//        k <<= 1;
//        sort(a + 1, a + k + 1, [] (int &x, int &y) { return st[x] < st[y]; });
//        S.push(a[1]);
//        for(int i = 2; i <= k; i++) if (a[i] != a[i - 1]) {
//            while (ed[S.top()] < st[a[i]]) S.pop();
//            ke[S.top()].push_back(a[i]);
//            S.push(a[i]);
//        }
//        solve(a[1]);
//        cout << res << endl;
//        for(int i = 1; i <= k; i++) mark1[a[i]] = mark2[a[i]] = 0, ke[a[i]].clear();
//    }
//}

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