Submission #729664

#	Time	Username	Problem	Language	Result	Execution time	Memory
729664		hgmhc	Factories (JOI14_factories)	C++17	100 / 100	4411 ms	184336 KiB

factories

#include "factories.h"
#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 centroid_tree {
    int sub[N], par[N], lev[N];
    ll dp[N][20];
    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;
    }
    void dfs(int l, int s, int e = -1, ll d = 0) {
        dp[s][lev[s]-l] = d;
        for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
            dfs(l,u,s,d+w);
        }
    }
    ll dist[N]{};
    void build(int level = 0, int s = 0, int e = -1) {
        size_calc(s);
        int c = centroid(sub[s],s);
        dist[c] = INF;
        erased[c] = true, par[c] = e;
        lev[c] = level;
        for (auto [u,w] : adj[c]) if (not erased[u]) {
            build(level+1,u,c);
        }
        erased[c] = false;
        for (auto [u,w] : adj[c]) if (not erased[u]) {
            dfs(level,u,c,w);
        }
    }
    ll query(int x) {
        ll res = INF;
        for (int y = x, i = 0; y != -1; y = par[y], ++i) {
            mup(res, dist[y]+dp[x][i]);
        }
        return res;
    }
    void update(int x) {
        for (int y = x, i = 0; y != -1; y = par[y], ++i) {
            mup(dist[y], dp[x][i]);
        }
    }
    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});
    }
    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: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67