oj.uz

답안 #529874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529874 2022-02-23T22:45:15 Z Lobo 공장들 (JOI14_factories) C++17
100 / 100
 4484 ms 490512 KB 
#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;
//     }


// }

Compilation message

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12804 KB Output is correct
2 Correct 313 ms 24388 KB Output is correct
3 Correct 457 ms 24412 KB Output is correct
4 Correct 421 ms 24360 KB Output is correct
5 Correct 426 ms 24704 KB Output is correct
6 Correct 194 ms 24300 KB Output is correct
7 Correct 465 ms 24332 KB Output is correct
8 Correct 440 ms 24364 KB Output is correct
9 Correct 420 ms 24772 KB Output is correct
10 Correct 191 ms 24324 KB Output is correct
11 Correct 446 ms 24372 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 2523 ms 433184 KB Output is correct
3 Correct 3366 ms 436548 KB Output is correct
4 Correct 1263 ms 456092 KB Output is correct
5 Correct 3512 ms 489388 KB Output is correct
6 Correct 3444 ms 456204 KB Output is correct
7 Correct 1334 ms 118916 KB Output is correct
8 Correct 436 ms 120436 KB Output is correct
9 Correct 1147 ms 123928 KB Output is correct
10 Correct 1293 ms 120308 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12804 KB Output is correct
2 Correct 313 ms 24388 KB Output is correct
3 Correct 457 ms 24412 KB Output is correct
4 Correct 421 ms 24360 KB Output is correct
5 Correct 426 ms 24704 KB Output is correct
6 Correct 194 ms 24300 KB Output is correct
7 Correct 465 ms 24332 KB Output is correct
8 Correct 440 ms 24364 KB Output is correct
9 Correct 420 ms 24772 KB Output is correct
10 Correct 191 ms 24324 KB Output is correct
11 Correct 446 ms 24372 KB Output is correct
12 Correct 8 ms 12620 KB Output is correct
13 Correct 2523 ms 433184 KB Output is correct
14 Correct 3366 ms 436548 KB Output is correct
15 Correct 1263 ms 456092 KB Output is correct
16 Correct 3512 ms 489388 KB Output is correct
17 Correct 3444 ms 456204 KB Output is correct
18 Correct 1334 ms 118916 KB Output is correct
19 Correct 436 ms 120436 KB Output is correct
20 Correct 1147 ms 123928 KB Output is correct
21 Correct 1293 ms 120308 KB Output is correct
22 Correct 3146 ms 458868 KB Output is correct
23 Correct 3210 ms 461564 KB Output is correct
24 Correct 4407 ms 462272 KB Output is correct
25 Correct 4416 ms 466172 KB Output is correct
26 Correct 4318 ms 462396 KB Output is correct
27 Correct 4354 ms 490512 KB Output is correct
28 Correct 1383 ms 466496 KB Output is correct
29 Correct 4284 ms 462156 KB Output is correct
30 Correct 4484 ms 461136 KB Output is correct
31 Correct 4294 ms 462020 KB Output is correct
32 Correct 1245 ms 125020 KB Output is correct
33 Correct 451 ms 120688 KB Output is correct
34 Correct 1029 ms 116584 KB Output is correct
35 Correct 1058 ms 116444 KB Output is correct
36 Correct 1235 ms 117376 KB Output is correct
37 Correct 1320 ms 117236 KB Output is correct