Submission #529731

#	Time	Username	Problem	Language	Result	Execution time	Memory
529731		Lobo	Factories (JOI14_factories)	C++17	15 / 100	8087 ms	171408 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 500050

int n, mn[maxn], szfc[maxn], block[maxn], d[maxn], p[maxn][23], h[maxn], pc[maxn];
vector<int> vfc;
vector<pair<int,int>> g[maxn];

void dfsfc(int u, int ant) {
    szfc[u] = 1;
    vfc.pb(u);

    for(auto V : g[u]) {
        int v = V.fr;
        if(v == ant || block[v]) continue;
        dfsfc(v,u);
        szfc[u]+= szfc[v];
    }
}

void dfslca(int u, int ant) {
    p[u][0] = ant;
    for(int i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
    }

    for(auto V : g[u]) {
        int v = V.fr;
        int w = V.sc;
        if(v == ant) continue;
        h[v] = h[u]+1;
        d[v] = d[u]+w;
        dfslca(v,u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u,v);

    for(int i = 20; i >= 0; i--) {
        if(h[p[u][i]] >= h[v]) {
            u = p[u][i];
        }
    }

    if(u == v) return u;

    for(int i = 20; i >= 0; i--) {
        if(p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }

    return p[u][0];
}

int fcent(int beg) {
    vfc.clear();
    dfsfc(beg,beg);
    int cent;

    for(auto u : vfc) {
        bool ok = true;
        if(szfc[beg]-szfc[u] > szfc[beg]/2) ok = false;

        for(auto V : g[u]) {
            int v = V.fr;
            if(block[v]) continue;
            if(szfc[v] > szfc[u]) continue;
            if(szfc[v] > szfc[beg]/2) ok = false;
        }

        if(ok) cent = u;
    }

    block[cent] = 1;
    for(auto V : g[cent]) {
        int v = V.fr;
        if(block[v]) continue;
        pc[fcent(v)] = cent;
    }

    return cent;
}

int Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    int ans = inf;
    for(int i = 0; i < S; i++) {
        int v = X[i];
        int dis = 0;
        int cnt = 0;
        while(v != -1) {
            cnt++;
            int dis = d[X[i]]+d[v]-2*d[lca(X[i],v)];
            mn[v] = min(mn[v],dis);
            v = pc[v];
        }

        assert(cnt <= 24);
    }

    for(int i = 0; i < T; i++) {
        int v = Y[i];
        int dis = 0;
        while(v != -1) {
            int dis = d[Y[i]]+d[v]-2*d[lca(Y[i],v)];
            ans = min(ans, mn[v]+dis);
            v = pc[v];
        }
    }

    for(int i = 0; i < S; i++) {
        int v = X[i];
        int dis = 0;
        while(v != -1) {
            mn[v] = inf;
            v = pc[v];
        }
    }

    return ans;
}

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

    for(int i = 0; i < n; i++) {
        pc[i] = -1;
        mn[i] = inf;
    }
    fcent(0);
    dfslca(0,0);
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int32_t, int32_t*, int32_t, int32_t*)':
factories.cpp:104:13: warning: unused variable 'dis' [-Wunused-variable]
  104 |         int dis = 0;
      |             ^~~
factories.cpp:118:13: warning: unused variable 'dis' [-Wunused-variable]
  118 |         int dis = 0;
      |             ^~~
factories.cpp:128:13: warning: unused variable 'dis' [-Wunused-variable]
  128 |         int dis = 0;
      |             ^~~
factories.cpp: In function 'long long int fcent(long long int)':
factories.cpp:74:9: warning: 'cent' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     int cent;
      |         ^~~~

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