Submission #729631

#	Time	Username	Problem	Language	Result	Execution time	Memory
729631		hgmhc	Factories (JOI14_factories)	C++17	0 / 100	35 ms	12620 KiB

factories

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const ll INF = 1e18;
const int N = 5e5+3, Q = 1e5+3;
int n, q;
vector<ii> adj[N];

namespace tree {
    int spt[N][20], lev[N];
    ll depth[N];
    void dfs(int s = 0, int e = -1) {
        spt[s][0] = e;
        for (auto [u,w] : adj[s]) if (u != e) {
            depth[u] += depth[s]+w, lev[u] = lev[s]+1, dfs(u,s);
        }
    }
    void build() {
        dfs();
        rep(j,1,19) rep(i,0,n-1) spt[i][j] = spt[spt[i][j-1]][j-1];
    }
    int lca(int x, int y) {
        if (lev[x] > lev[y]) swap(x,y);
        rep(i,0,19) if ((lev[y]-lev[x])>>i&1) y = spt[y][i];
        if (x == y) return x;
        per(i,0,19) {
            if (spt[x][i] != spt[y][i])
                x = spt[x][i], y = spt[y][i];
        }
        return spt[x][0];
    }
    ll dist(int x, int y) { return depth[x]+depth[y]-2*depth[lca(x,y)]; }
}

namespace centroid_tree {
    int sub[N], par[N];
    bool erased[N];
    void size_calc(int s, int e = -1) {
        sub[s] = 1;
        for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
            size_calc(u,s), sub[s] += sub[u];
        }
    }
    int centroid(int S, int s, int e = -1) {
        for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
            if (sub[u] > S/2) return centroid(S,u,s);
        }
        return s;
    }
    ll dist[N]{};
    void build(int s = 0, int e = -1) {
        size_calc(s);
        int c = centroid(sub[s],s);
        dist[c] = INF;
        erased[c] = true, par[c] = e;
        for (auto [u,w] : adj[c]) if (not erased[u]) {
            build(u,c);
        }
    }
    ll query(int x) {
        ll res = INF;
        for (int y = x; y != -1; y = par[y]) {
            mup(res, dist[y]+tree::dist(x,y));
        }
        return res;
    }
    void update(int x) {
        for (int y = x; y != -1; y = par[y]) {
            mup(dist[y], tree::dist(x,y));
        }
    }
    void clear(int x) {
        for (int y = x; y != -1; y = par[y]) dist[y] = INF;
    }
};

void Init(int N, int A[], int B[], int D[]) {
    rep(i,0,N-2) {
        auto [u,v,w] = tie(A[i],B[i],D[i]);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    tree::build();
    centroid_tree::build();
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> x(S);
    ll ans = INF;
    rep(i,0,S-1) centroid_tree::update(X[i]);
    rep(i,0,T-1) mup(ans, centroid_tree::query(Y[i]));
    rep(i,0,S-1) centroid_tree::clear(X[i]);
    return ans;
}

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