Submission #993775

#	Time	Username	Problem	Language	Result	Execution time	Memory
993775		Valaki2	Factories (JOI14_factories)	C++14	100 / 100	3542 ms	264640 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 5e5;
const ll inf = 1e16 + 42;

struct edge {
    int to;
    ll wei;
    int subtree_size;
    edge() : to(0), wei(0ll), subtree_size(0) {}
    edge(int to_, ll wei_, int subtree_size_) :
        to(to_), wei(wei_), subtree_size(subtree_size_) {}
};

const int logn = 20;

int n;
vector<edge > graph[1 + maxn];
bool done[1 + maxn];
vector<int> ctree[1 + maxn];
int cpar[1 + maxn];
int croot;
int dep[1 + maxn];
int lift[1 + maxn][logn];
ll pref[1 + maxn];
ll centdist[1 + maxn][logn];
int level[1 + maxn];

int dfs_subtree(int cur, int par, const int &all_size) {
    int cur_size = 1;
    for(edge &nei : graph[cur]) {
        if(nei.to != par && !done[nei.to]) {
            int this_size = dfs_subtree(nei.to, cur, all_size);
            nei.subtree_size = this_size;
            cur_size += this_size;
        }
    }
    for(edge &nei : graph[cur]) {
        if(nei.to == par) {
            nei.subtree_size = all_size - cur_size;
            break;
        }
    }
    return cur_size;
}

void dfs_dist(int cur, int par, ll cur_dist, const int &cur_level) {
    centdist[cur][cur_level] = cur_dist;
    for(edge nei : graph[cur]) {
        if(nei.to != par && !done[nei.to]) {
            dfs_dist(nei.to, cur, cur_dist + nei.wei, cur_level);
        }
    }
}

void decompose(int cur, int prev_centroid, int all_size) {
    dfs_subtree(cur, -1, all_size);
    while(true) {
        pii best = mp(-1, all_size / 2);
        for(edge nei : graph[cur]) {
            if(!done[nei.to]) {
                pii cur_pair = mp(nei.to, nei.subtree_size);
                if(cur_pair.se > best.se) {
                    best = cur_pair;
                }
            }
        }
        /*cout << cur << " " << prev_centroid << " " << all_size << endl;
        for(edge e : graph[1]) {
            cout << e.to << " " << e.subtree_size << endl;
        }*/
        if(best.fi == -1) {
            break;
        }
        cur = best.fi;
    }
    // centroid: cur
    cpar[cur] = prev_centroid;
    if(prev_centroid != -1) {
        ctree[prev_centroid].pb(cur);
        level[cur] = level[cpar[cur]] + 1;
    } else {
        croot = cur;
    }
    dfs_dist(cur, -1, 0, level[cur]);
    done[cur] = true;
    for(edge nei : graph[cur]) {
        if(!done[nei.to]) {
            decompose(nei.to, cur, nei.subtree_size);
        }
    }
}

void dfs_depth(int cur) {
    for(edge nei : graph[cur]) {
        if(nei.to != lift[cur][0]) {
            lift[nei.to][0] = cur;
            dep[nei.to] = dep[cur] + 1;
            pref[nei.to] = pref[cur] + nei.wei;
            dfs_depth(nei.to);
        }
    }
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) {
        swap(a, b);
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(dep[b] - (1 << j) >= dep[a]) {
            b = lift[b][j];
        }
    }
    if(a == b) {
        return a;
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(lift[a][j] != lift[b][j]) {
            a = lift[a][j];
            b = lift[b][j];
        }
    }
    return lift[b][0];
}

ll dist(int a, int b) {
    int c = lca(a, b);
    return pref[a] + pref[b] - 2 * pref[c];
}

ll nearest[1 + maxn];
bool to_reset[1 + maxn];
vector<int> reset;

void Init(signed N, signed A[], signed B[], signed D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++) {
        int a = A[i], b = B[i], d = D[i];
        a++;
        b++;
        graph[a].pb(edge(b, d, 0));
        graph[b].pb(edge(a, d, 0));
    }
    /*for(int i = 1; i <= n; i++) {
        cout << i << endl;
        for(edge e : graph[i]) {
            cout << e.to << " " << e.wei << endl;
        }
    }
    return;*/
    decompose(1, -1, n);
    lift[1][0] = 1;
    dfs_depth(1);
    for(int j = 1; j < logn; j++) {
        for(int i = 1; i <= n; i++) {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        nearest[i] = inf;
    }
    /*for(int i = 1; i <= n; i++) {
        cout << cpar[i] << " ";
    }
    cout << endl;*/
}

void upd(int cur) {
    int centroid = cur;
    while(centroid != -1) {
        if(!to_reset[centroid]) {
            to_reset[centroid] = true;
            reset.pb(centroid);
        }
        nearest[centroid] = min(nearest[centroid], centdist[cur][level[centroid]]);
        centroid = cpar[centroid];
    }
}

ll query(int cur) {
    int centroid = cur;
    ll res = inf;
    while(centroid != -1) {
        res = min(res, centdist[cur][level[centroid]] + nearest[centroid]);
        centroid = cpar[centroid];
    }
    return res;
}

ll Query(signed S, signed X[], signed T, signed Y[]) {
    vector<int> a, b;
    for(int i = 0; i < S; i++) {
        a.pb(X[i] + 1);
    }
    for(int j = 0; j < T; j++) {
        b.pb(Y[j] + 1);
    }
    for(int y : b) {
        upd(y);
    }
    ll ans = inf;
    for(int x : a) {
        ans = min(ans, query(x));
    }
    for(int r : reset) {
        to_reset[r] = false;
        nearest[r] = inf;
    }
    reset.clear();
    return ans;
}

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