Submission #821148

#	Time	Username	Problem	Language	Result	Execution time	Memory
821148		Alihan_8	Factories (JOI14_factories)	C++17	0 / 100	8076 ms	88480 KiB

factories

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

const long long inf = 1e15 + 1;

const int N = 5e5 + 1;

vector <pair<int,int>> g[N];

int n, up[N][20], d[N];

long long dis[N];

void dfs(int x, int par){
    up[x][0] = par;
    for ( int i = 1; i < 20; i++ ){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for ( auto [to, w]: g[x] ){
        if ( to != par ){
            dis[to] = dis[x] + w;
            d[to] = d[x] + 1;
            dfs(to, x);
        }
    }
}

int lca(int x, int y){
    if ( d[x] < d[y] ) swap(x, y);
    int dif = d[x] - d[y];
    for ( int i = 0; i < 20; i++ ){
        if ( dif >> i & 1 ){
            x = up[x][i];
        }
    }
    if ( x == y ){
        return x;
    }
    for ( int i = 19; i >= 0; i-- ){
        if ( up[x][i] != up[y][i] ){
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

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

long long Query(int S, int X[], int T, int Y[]) {
    auto get = [&](int u, int v){
        return dis[u] + dis[v] - dis[lca(u, v)] * 2;
    };
    long long ans = inf;
    for ( int i = 0; i < S; i++ ){
        for ( int j = 0; j < T; j++ ){
            chmin(ans, get(X[i], Y[j]));
        }
    }
    return ans;
}

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