Submission #230666

#	Time	Username	Problem	Language	Result	Execution time	Memory
230666		arbor	Factories (JOI14_factories)	C++14	0 / 100	19 ms	12800 KiB

factories

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define lc (i << 1)
#define rc (i << 1 | 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 5e5 + 5, LN = 17, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
vector<pii> g[MN];
int sz[MN], par[MN], dep[MN], qid[MN], id = 1;
ll dis[20][MN], dp[MN];
bool vis[MN];

int get_sz(int u, int p) {
    sz[u] = 1;
    for (pii e : g[u]) if (e.first != p && !vis[e.first])
        sz[u] += get_sz(e.first, u);
    return sz[u];
}

int centroid(int u, int p, int s) {
    for (pii e : g[u]) if (e.first != p && !vis[e.first] && sz[e.first] > s / 2)
        return centroid(e.first, u, s);
    return u;
}

void dfs(int u, int p, ll d, int lvl) {
    dis[lvl][u] = d;
    for (pii e : g[u]) if (e.first != p && !vis[e.first])
        dfs(e.first, u, d + e.second, lvl);
}

void go(int u, int p, int lvl) {
    int c = centroid(u, -1, get_sz(u, -1));
    dep[c] = lvl;
    par[c] = p;
    dfs(c, -1, 0, lvl);
    vis[c] = true;
    for (pii e : g[c])
        if (!vis[e.first])
            go(e.first, c, lvl + 1);
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    go(0, -1, 0);
}

ll Query(int S, int X[], int T, int Y[]) {
    ll ret = LLONG_MIN;
    for (int i = 0; i < S; i++) {
        int cur = X[i];
        while (cur != -1) {
            if (qid[cur] != id) dp[cur] = dis[dep[cur]][X[i]], qid[cur] = id;
            else dp[cur] = min(dp[cur], dis[dep[cur]][X[i]]);
            cur = par[cur];
        }
    }
    for (int i = 0; i < T; i++) {
        int cur = Y[i];
        while (cur != -1) {
            if (qid[cur] == id) ret = min(ret, dp[cur] + dis[dep[cur]][Y[i]]);
            cur = par[cur];
        }
    }
    id++;
    return ret;
}

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