Submission #821326

#	Time	Username	Problem	Language	Result	Execution time	Memory
821326		Alihan_8	Factories (JOI14_factories)	C++17	0 / 100	118 ms	192616 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, K = 21, M = N * 2 + 1;

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

vector <int> cPar[N], have;

vector <long long> res(N, inf);

int pos[M], timer = -1, tin[N], sub[N], now;

bool vis[N];

long long dis[N], sp[K][M];

void dfs(int x, int par){
    pos[++timer] = x;
    tin[x] = timer;
    for ( auto [to, w]: g[x] ){
        if ( to != par ){
            dis[to] = dis[x] + w;
            dfs(to, x);
            pos[++timer] = x;
        }
    }
}

long long lca(int l, int r){
    int lg = __lg(r - l + 1), k = 1 << lg;
    return min(sp[lg][l], sp[lg][r + 1 - k]);
}

long long get(int u, int v){
    if ( tin[u] > tin[v] ){
        swap(u, v);
    }
    return dis[u] + dis[v] - lca(tin[u], tin[v]) * 2;
}

void calcS(int x, int par){
    sub[x] = 1;
    have.pb(x);
    for ( auto [to, w]: g[x] ){
        if ( to != par and !vis[to] ){
            calcS(to, x);
            sub[x] += sub[to];
        }
    }
}

int centroid(int x, int par){
    for ( auto [to, w]: g[x] ){
        if ( !vis[to] and to != par ){
            if ( sub[to] > now / 2 ){
                return centroid(to, x);
            }
        }
    }
    return x;
}

void decompose(int x){
    have.clear();
    calcS(x, -1);
    now = sub[x];
    auto u = centroid(x, -1);
    for ( auto &v: have ){
        cPar[v].pb(u);
    }
    vis[u] = true;
    for ( auto [to, w]: g[u] ){
        if ( !vis[to] ){
            decompose(to);
        }
    }
}

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]});
    }
    dfs(0, -1);
    for ( int i = 0; i < M; i++ ){
        sp[0][i] = dis[pos[i]];
    }
    for ( int i = 1; i < K; i++ ){
        int k = 1 << i - 1;
        for ( int j = 0; j < M; j++ ){
            sp[i][j] = min(sp[i - 1][j], sp[i - 1][min(M - 1, j + k)]);
        }
    }
    decompose(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector <int> C;
    for ( int u = 0; u < S; u++ ){
        for ( auto v: cPar[u] ){
            chmin(res[v], get(X[u], v));
            C.pb(v);
        }
    }
    long long ans = inf;
    for ( int i = 0; i < T; i++ ){
        for ( auto u: cPar[i] ){
            chmin(ans, res[u] + get(Y[i], u));
        }
    }
    for ( auto &u: C ){
        res[u] = inf;
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:116:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  116 |         int k = 1 << i - 1;
      |                      ~~^~~

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