제출 #529874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529874		Lobo	공장들 (JOI14_factories)	C++17	100 / 100	4484 ms	490512 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], h[maxn], pc[maxn], tin[maxn], tout[maxn];
pair<int,int> mnr[2*maxn][23], mnl[2*maxn][23];
long long d[maxn], mn[maxn];
vector<int> vfc;
vector<pair<int,int>> g[maxn], el;

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) {
    tin[u] = el.size();
    el.pb(mp(h[u],u));
    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);
        el.pb(mp(h[u],u));
    }
    tout[u] = el.size()-1;
}

int lca(int u, int v) {
    if(tin[u] >= tin[v] && tout[u] <= tout[v]) {
        return v;
    }
    else if(tin[v] >= tin[u] && tout[v] <= tout[u]) {
        return u;
    }

    if(tin[u] > tin[v]) {
        swap(u,v);
    }
    int l = tout[u];
    int r = tin[v];

    int p = 31-__builtin_clz(r-l+1);
    auto x = min(mnr[l][p], mnl[r][p]);
    return x.sc;
}

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

    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);
    dfslca(0,0);
    for(int i = 0; i < el.size(); i++) {
        mnr[i][0] = el[i];
    }
    for(int j = 1; j <= 21; j++) {
        for(int i = 0; i < el.size(); i++) {
            mnr[i][j] = min(mnr[i][j-1],mnr[min((int) el.size()-1, i+(1<<(j-1)))][j-1]);  
        }
    }

    for(int i = 0; i < el.size(); i++) {
        mnl[i][0] = el[i];
    }
    for(int j = 1; j <= 21; j++) {
        for(int i = 0; i < el.size(); i++) {
            mnl[i][j] = min(mnl[i][j-1],mnl[max(0, i-(1<<(j-1)))][j-1]);  
        }
    }
}

// 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 'void Init(int32_t, int32_t*, int32_t*, int32_t*)':
factories.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i = 0; i < el.size(); i++) {
      |                    ~~^~~~~~~~~~~
factories.cpp:145:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(int i = 0; i < el.size(); i++) {
      |                        ~~^~~~~~~~~~~
factories.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0; i < el.size(); i++) {
      |                    ~~^~~~~~~~~~~
factories.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for(int i = 0; i < el.size(); i++) {
      |                        ~~^~~~~~~~~~~

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