Submission #1280896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280896		dex111222333444555	Factories (JOI14_factories)	C++20	100 / 100	3637 ms	342740 KiB

factories

void Init(int N, int A[], int B[], int D[]);
long long Query(int S, int X[], int T, int Y[]);
#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second;
using namespace std;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
const int MAXN = 5e5 + 5;
const long long inf = 1e18 + 3;
int numNode, numQuery, companyU, companyV, factoryU[MAXN], factoryV[MAXN], sz[MAXN];
bool del[MAXN];
long long best[MAXN];
vector<ii> adj[MAXN];
vector<pair<int, long long> > can[MAXN];

int getSize(int u, int par = 0){
    sz[u] = 1;
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        sz[u] += getSize(v, u);
    }
    return sz[u];
}

int getCentroid(int sizeU, int u, int par = 0){
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        if (sz[v] > (sizeU >> 1)) return getCentroid(sizeU, v, u);
    }
    return u;
}

void addCan(int u, const int &centroid, long long dist, int par = 0){
    can[u].push_back({centroid, dist});
    for(ii x: adj[u]) if (!del[x.fi] && x.fi != par) {
        int v = x.fi, w = x.se;
        addCan(v, centroid, dist + w, u);
    }
}

void decomp(int u = 1){
    int centroid = getCentroid(getSize(u), u);
    del[centroid] = 1;
    for(ii x: adj[centroid]) if (!del[x.fi]) {
        int v = x.fi, w = x.se;
        addCan(v, centroid, w);
    }
    for(ii x: adj[centroid]) if (!del[x.fi]){
        int v = x.fi, w = x.se;
        decomp(v);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    numNode = N;
    int u, v;
    for(int i = 0; i < N - 1; i++){
        u = A[i]; v = B[i];
        u++; v++;
        adj[u].push_back({v, D[i]});
        adj[v].push_back({u, D[i]});
    }
    decomp();
    for(int u = 1; u <= numNode; u++) can[u].push_back({u, 0});
    memset(best, 0x3f, sizeof best);
}

void operation(int u, bool type){
    best[u] = (type ? inf: 0);
    for(pair<int, long long> x: can[u]){
        int centroid = x.fi;
        long long dist = x.se;
        if (type) best[centroid] = inf;
        else minimize(best[centroid], dist);
    }
}

long long query(int u){
    long long res = inf;
    for(pair<int, long long> x: can[u]){
        int centroid = x.fi;
        long long dist = x.se;
        minimize(res, dist + best[centroid]);
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < S; i++) X[i]++;
    for(int i = 0; i < T; i++) Y[i]++;
    for(int i = 0; i < S; i++) operation(X[i], 0);
    long long res = inf;
    for(int i = 0; i < T; i++) minimize(res, query(Y[i]));
    for(int i = 0; i < S; i++) operation(X[i], 1);
    return res;
}

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