제출 #529761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529761		Lobo	공장들 (JOI14_factories)	C++17	0 / 100	47 ms	12580 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, szfc[maxn], block[maxn], p[maxn][23], h[maxn], pc[maxn];
long long d[maxn], mn[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;
}

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

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

    for(int i = 0; i < S; i++) {
        int v = X[i];
        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);

    for(int i = 0; i < n; i++) {
        cout << i << " -> " << pc[i] << endl;
    }
    dfslca(0,0);
}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
//     //freopen("out.out", "w", stdout);

//     int32_t N, Q; cin >> N >> Q;
//     int32_t A[N-1], B[N-1], D[N-1];
//     for(int i = 0; i < N-1; i++) {
//         cin >> A[i] >> B[i] >> D[i];
//     }

//     Init(N,A,B,D);

//     while(Q--) {
//         int32_t S, T; cin >> S >> T;
//         int32_t X[S], Y[T];
//         for(int i = 0; i < S; i++) cin >> X[i];
//         for(int i = 0; i < T; i++) cin >> Y[i];

//         cout << Query(S,X,T,Y) << endl;
//     }


// }

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'int fcent(int)':
factories.cpp:75:9: warning: 'cent' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     int cent;
      |         ^~~~

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