Submission #230370

#	Time	Username	Problem	Language	Result	Execution time	Memory
230370		arbor	Factories (JOI14_factories)	C++14	100 / 100	4969 ms	171996 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 = 19, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
vector<pii> g[MN];
int sz[MN], par[MN], lvl[MN];
ll down[LN][MN]; // dis from a centroid at lvl j, to a node i
bool vis[MN];
ll mn[MN]; // mn dis from centroid i, to any factory of first kind in children
int qid[MN], id = 1;

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 dis, int d) {
    down[d][u] = dis;
    for (pii e : g[u]) if (e.first != p && !vis[e.first])
            dfs(e.first, u, dis + e.second, d);
}

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

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

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int cur = X[i];
        while (cur != -1) {
            if (qid[cur] != id) qid[cur] = id, mn[cur] = down[lvl[cur]][X[i]];
            else mn[cur] = min(mn[cur], down[lvl[cur]][X[i]]);
            cur = par[cur];
        }
    }
    ll ret = LLONG_MAX;
    for (int i = 0; i < T; i++) {
        int cur = Y[i];
        while (cur != -1) {
            if (qid[cur] == id) ret = min(ret, mn[cur] + down[lvl[cur]][Y[i]]);
            cur = par[cur];
        }
    }
    id++;
    return ret;
}

/*
int main() {
    int N, Q;
    cin >> N >> Q;
    int a[N + 1], b[N + 1], d[N + 1];
    for (int i = 0; i < N - 1; i++) cin >> a[i] >> b[i] >> d[i];
    Init(N, a, b, d);
    for (int i = 0; i < Q; i++) {
        int s, t;
        cin >> s >> t;
        int x[s + 1], y[t + 1];
        for (int j = 0; j < s; j++) cin >> x[j];
        for (int j = 0; j < t; j++) cin >> y[j];
        cout << Query(s, x, t, y) << '\n';
    }
    return 0;
}
*/

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