Submission #212463

#	Time	Username	Problem	Language	Result	Execution time	Memory
212463		ChrisT	Factories (JOI14_factories)	C++17	15 / 100	8100 ms	184436 KiB

factories

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+3, LOG = 19, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int op[MN][LOG], od[MN], sz[MN], p[MN]; bool done[MN]; ll down[MN], up[MN], oup[MN][LOG];
vector<pii> adj[MN];
void prep (int cur) {
    for (pii i : adj[cur]) if (i.first != op[cur][0]) {
        op[i.first][0] = cur; oup[i.first][0] = i.second; od[i.first] = od[cur] + 1;
        for (int j = 1; j < LOG; j++)
            if (op[i.first][j-1])
                op[i.first][j] = op[op[i.first][j-1]][j-1], oup[i.first][j] = oup[i.first][j-1] + oup[op[i.first][j-1]][j-1];
        prep(i.first);
    }
}
ll dist (int a, int b) {
    if (od[a] < od[b]) swap(a,b);
    ll ret = 0;
    for (int i = LOG-1; i >= 0; i--)
        if (op[a][i] && od[op[a][i]] >= od[b])
            ret += oup[a][i], a = op[a][i];
    if (a == b) return ret;
    for (int i = LOG-1; i >= 0; i--)
        if (op[a][i] && op[b][i] && op[a][i] != op[b][i])
            ret += oup[a][i] + oup[b][i], a = op[a][i], b = op[b][i];
    return ret + oup[a][0] + oup[b][0];
}
int dfs (int cur, int par = -1) {
    sz[cur] = 1;
    for (pii i : adj[cur]) if (!done[i.first] && i.first != par) {
        sz[cur] += dfs(i.first,cur);
    }
    return sz[cur];
}
int findcent (int cur, int tot, int par = -1) {
    for (pii i : adj[cur]) {
        if (i.first != par && !done[i.first] && sz[i.first] > (tot>>1))
            return findcent(i.first,tot,cur);
    }
    return cur;
}
void maketree (int cur, int lst = 0) {
    dfs(cur);
    int cent = findcent(cur,sz[cur]);
    done[cent] = 1;
    p[cent] = lst;
    for (pii i : adj[cent]) if (!done[i.first]) maketree(i.first,cent);
}
void Init (int n, int *a, int *b, int *d) {
    for (int i = 0; i < n-1; i++) {
        adj[++a[i]].emplace_back(++b[i],d[i]);
        adj[b[i]].emplace_back(a[i],d[i]);
    }
    prep(1);
    maketree(1);
    memset(down,0x3f,sizeof down);
}
ll Query (int s, int *x, int t, int *y) {
    ll ret = LLONG_MAX;
    for (int i = 0; i < s; i++) {
        int st = ++x[i], cur = st;
        while (cur) {
            down[cur] = min(down[cur],dist(cur,st));
            cur = p[cur];
        }
    }
    for (int i = 0; i < t; i++) {
        int st = ++y[i], cur = st;
        while (cur) {
            ret = min(ret,dist(st,cur)+down[cur]);
            cur = p[cur];
        }
    }
    assert(ret != LLONG_MAX);
    for (int i = 0; i < s; i++) {
        int cur = x[i];
        while(cur) {
            down[cur] = 1e18;
            cur = p[cur];
        }
    }
    return ret;
}

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