Submission #422423

#	Time	Username	Problem	Language	Result	Execution time	Memory
422423		Hideo	Factories (JOI14_factories)	C++17	100 / 100	6143 ms	341280 KiB

factories

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

using namespace std;

#define ll long long
#define pb push_back
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define pi pair < int, int >

const int MN = 5e5 + 7;
const ll INF = 1e18 + 7;

ll d[MN];
int sb[MN], mx[MN], del[MN];
int n;

vector < pi > g[MN];
vector < pair < int, ll > > q[MN];

void dfs (int v, int sz, int p = 0){
    sb[v] = 1;
    mx[v] = 0;
    for (pi to : g[v]){
        if (!del[to.fr] && to.fr != p){
            dfs(to.fr, sz, v);
            sb[v] += sb[to.fr];
            mx[v] = max(mx[v], sb[to.fr]);
        }
    }
    mx[v] = max(mx[v], sz - sb[v]);
//    cout << v << ' ' << sb[v] << ' '  << mx[v] << endl;
}

int fc (int v, int sz){
    while (true){
        int nv = v;
        if (mx[v] <= sz / 2)
            break;
        for (pi to : g[v]){
            if (!del[to.fr] && mx[to.fr] < mx[v]){
                v = to.fr;
                break;
            }
        }
        if (nv == v)
            break;
    }
    return v;
}

void mark (int v, int st, ll dis = 0, int p = 0){
    q[v].pb({st, dis});
    for (pi to : g[v]){
        if (to.fr != p && !del[to.fr]){
            mark(to.fr, st, dis + to.sc, v);
        }
    }
}

void cent (int v, int sz){
    dfs(v, sz);
    v = fc(v, sz);
    mark(v, v);
    del[v] = 1;
    for (pi to : g[v]){
        if (!del[to.fr]){
            if (sb[to.fr] < sb[v])
                cent(to.fr, sb[to.fr]);
            else
                cent(to.fr, sz - sb[v]);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++){
        g[A[i] + 1].pb({B[i] + 1, D[i]});
        g[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    cent(1, n);
    memset(d, 0x3f3f3f3f, sizeof(d));
}

long long Query(int S, int X[], int T, int Y[]){
    ll ans = INF;
    for (int i = 0; i < S; i++){
        int v = X[i] + 1;
        for (auto it : q[v]){
            d[it.fr] = min(d[it.fr], it.sc);
        }
    }
    for (int i = 0; i < T; i++){
        int v = Y[i] + 1;
        for (auto it : q[v]){
            ans = min(ans, d[it.fr] + it.sc);
        }
    }
    for (int i = 0; i < S; i++){
        int v = X[i] + 1;
        for (auto it : q[v]){
            d[it.fr] = INF;
        }
    }
    return ans;
}

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