Submission #1135321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135321		lopkus	Factories (JOI14_factories)	C++20	100 / 100	2919 ms	158956 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;

vector<vector<pii>> g;
vector<int> sz;
vector<bool> used;

void fill_sz(int v, int pr){
    sz[v] = 1;
    for (auto [i, w]: g[v]){
        if (i == pr || used[i]) continue;
        fill_sz(i, v);
        sz[v] += sz[i];
    }
}

int find(int v, int pr, int& S){
    for (auto [i, w]: g[v]){
        if (i == pr || used[i]) continue;
        if (2 * sz[i] >= S){
            return find(i, v, S);
        }
    }
    return v;
}

vector<vector<ll>> dist;
vector<int> dd, P;

void fill_dist(int v, int pr, int& k){
    for (auto [i, w]: g[v]){
        if (i == pr || used[i]) continue;
        dist[k][i] = dist[k][v] + w;
        fill_dist(i, v, k);
    }
}

void arvid(int v, int k){
    fill_sz(v, 0);
    v = find(v, 0, sz[v]);
    P[v] = k; used[v] = 1;
    dd[v] = dd[k] + 1;
    fill_dist(v, 0, dd[v]);

    for (auto [i, w]: g[v]){
        if (!used[i]){
            arvid(i, v);
        }
    }
}

vector<ll> f;

void Init(int n, int a[], int b[], int w[]){
    g.resize(n + 1);
    for (int i = 0; i < n - 1; i++){
        a[i]++; b[i]++;
        g[a[i]].pb({b[i], w[i]});
        g[b[i]].pb({a[i], w[i]});
    }
    sz.resize(n + 1);
    dd.resize(n + 1);
    used.resize(n + 1);
    P.resize(n + 1);
    dist.resize(log2(n) + 1);
    for (int i = 0; i <= log2(n); i++){
        dist[i].resize(n + 1);
    }
    dd[0] = -1; arvid(1, 0);
    f.assign(n + 1, inf);
}

vector<int> rem;

ll Query(int s, int x[], int t, int y[]){
    rem.clear();
    for (int i = 0; i < s; i++){
        int v = ++x[i];
        while (v > 0){
            f[v] = min(f[v], dist[dd[v]][x[i]]);
            rem.pb(v);
            v = P[v];
        }
    }
    ll out = inf;
    for (int i = 0; i < t; i++){
        int v = ++y[i];
        while (v > 0){
            out = min(out, dist[dd[v]][y[i]] + f[v]);
            v = P[v];
        }
    }
    for (int i: rem) f[i] = inf;
    return out;
}

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