Submission #603370

#	Time	Username	Problem	Language	Result	Execution time	Memory
603370		AA_Surely	Factories (JOI14_factories)	C++17	15 / 100	8016 ms	138228 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 5e5 + 7;
const LL INF = 1e18;
const int LOG = 20;

int n;
int par[N], sz[N];
int up[N][LOG], height[N];
bool vis[N];
LL dtr[N], opt[N];
VPII adj[N];

int getSz(int now, int p = -1) {
    sz[now] = 1;
    for(const auto &[on, v] : adj[now]) if (on != p && !vis[on]) sz[now] += getSz(on, now);
    return sz[now];
}

int getCent(int now, int p, int nn) {
    for(const auto &[on, v] : adj[now]) 
        if (on != p && !vis[on] && sz[on] > nn / 2) 
            return getCent(on, now, nn);
    return now;
}

void decomp(int now, int p = -1) {
    getSz(now);
    int c = getCent(now, -1, sz[now]);
    //cout << "centroid is " << c << endl;

    par[c] = p;
    vis[c] = 1;

    for(auto [on, w] : adj[c]) if (!vis[on]) decomp(on, c);
    return;
}

void dfs(int now, int p = -1, int h = 0, LL dist = 0) {
    up[now][0] = p;
    height[now] = h;
    dtr[now] = dist;
    for(auto [on, w] : adj[now]) if (on != p) dfs(on, now, h + 1, dist + w);
    return;
}

void Init(int nn, int A[], int B[], int D[]) {
    n = nn;
    F0R(i, n - 1) {
        adj[ A[i] ].PB({B[i], D[i]});
        adj[ B[i] ].PB({A[i], D[i]});
    }

    decomp(0);
    dfs(0);

    up[n][0] = n;
    FOR(k, 1, LOG) F0R(i, n + 1)
        up[i][k] = up[ up[i][k - 1] ][k - 1];
    
    //F0R(i, n) cout << par[i] << ' '; cout << endl;
    fill(opt, opt + n, INF);
    return;
}

int lca(int a, int b) {
    if (height[a] < height[b]) swap(a, b);
    R0F(i, LOG) if (height[a] - (1 << i) >= height[b]) a = up[a][i];
    if (a == b) return a;
    R0F(i, LOG) if (up[a][i] != up[b][i])
        a = up[a][i], b = up[b][i];
    return up[a][0];
}

LL dist(int a, int b) {
    int z = lca(a, b);
    return dtr[a] + dtr[b] - 2LL * dtr[z];
}

void add(int v) {
    int now = v;
    while(now != -1) {
        opt[now] = min(opt[now], dist(now, v));
        now = par[now];
    }
    return;
}

LL getMin(int v) {
    LL ret = INF;
    int now = v;
    while(now != -1) {
        ret = min(ret, opt[now] + dist(v, now));
        now = par[now];
    }
    return ret;
}

void rem(int v) {
    while(v != -1) {
        opt[v] = INF;
        v = par[v];
    }
}

LL Query(int s, int xs[], int t, int ys[]) {
    F0R(i, s) add(xs[i]);
    LL ans = INF;
    F0R(i, t) ans = min(ans, getMin(ys[i]));
    F0R(i, s) rem(xs[i]);
    return ans;
}

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