oj.uz

답안 #660347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660347 2022-11-21T17:18:14 Z rafatoa 공장들 (JOI14_factories) C++17
100 / 100
 6684 ms 259436 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")

#define F first
// #define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define double ld
// #define int long long
const long long INF = 4e18;

int n;
vector<vpi> adj;
vector<long long> d, dc, sub, par, best, vis, tin, eul;
vvi st;
vb del;

int tt = 0;

int lg2(int x){
    return 63-__builtin_clzll(x);
}

int cmp(int a, int b){
    return (d[a] < d[b] ? a : b);
}

int lca(int a, int b){
    if(tin[a] > tin[b]) swap(a, b);
    int len = tin[b]-tin[a]+1, lg = lg2(len);
    return cmp(st[tin[a]][lg], st[tin[b]-(1LL<<lg)+1][lg]);
}

long long dist(int a, int b){
    return dc[a]+dc[b]-2*dc[lca(a, b)];
}

void build(){
    d = dc = sub = par = vis = best = tin = vector<long long>(n+1);
    st = vvi(2*n-1, vi(21));
    del = vb(n+1);

    int time = 0;
    function<void(int, int)> dfs0 = [&](int s, int e){
        tin[s] = time;
        eul.pb(s); time++;
        for(auto [u, c]:adj[s]){
            if(u == e) continue;
            d[u] = d[s]+1;
            dc[u] = dc[s]+c;
            dfs0(u, s);
            eul.pb(s); time++;
        }
    };
    dfs0(1, 0);

    for(int i=0; i<2*n-1; i++) st[i][0] = eul[i];
    for(int j=1; j<=20; j++)
    for(int i=0; i+(1LL<<j)-1<2*n-1; i++)
        st[i][j] = cmp(st[i][j-1], st[i+(1LL<<(j-1))][j-1]);

    //START_CENTROID

    function<void(int, int)> dfs_sub = [&](int s, int e){
        sub[s] = 1;
        for(auto [u, c]:adj[s]){
            if(u == e || del[u]) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };

    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto [u, c]:adj[s])
            if(u != e && !del[u] && sub[u] > sz/2) return centroid(u, s, sz);
        return s;
    };

    function<void(int, int)> decompose = [&](int s, int p){
        dfs_sub(s, 0);
        int C = centroid(s, 0, sub[s]);
        par[C] = p;

        del[C] = 1;
        for(auto [u, c]:adj[C])
            if(!del[u]) decompose(u, C);
    };
    decompose(1, -1);

    //END_CENTROID
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    adj = vector<vpi>(n+1);
    for(int i=0; i<n-1; i++){
        adj[A[i]+1].pb({B[i]+1, D[i]});
        adj[B[i]+1].pb({A[i]+1, D[i]});
    }

    build();
}

long long Query(int S, int X[], int T, int Y[]){
    tt++;
    long long ans = INF;
    
    for(int i=0; i<T; i++){
        Y[i]++;
        int curr = Y[i];
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            best[curr] = min(best[curr], dist(curr, Y[i]));
            curr = par[curr];
        }
    }

    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i];
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            ans = min(ans, best[curr]+dist(curr, X[i]));
            curr = par[curr];
        }
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 724 KB Output is correct
2 Correct 389 ms 11492 KB Output is correct
3 Correct 501 ms 11568 KB Output is correct
4 Correct 480 ms 11572 KB Output is correct
5 Correct 595 ms 11888 KB Output is correct
6 Correct 251 ms 11488 KB Output is correct
7 Correct 481 ms 11568 KB Output is correct
8 Correct 540 ms 11476 KB Output is correct
9 Correct 604 ms 11868 KB Output is correct
10 Correct 228 ms 11532 KB Output is correct
11 Correct 497 ms 11588 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2834 ms 196312 KB Output is correct
3 Correct 3774 ms 200652 KB Output is correct
4 Correct 1099 ms 215340 KB Output is correct
5 Correct 5122 ms 259436 KB Output is correct
6 Correct 3780 ms 220544 KB Output is correct
7 Correct 2247 ms 62416 KB Output is correct
8 Correct 714 ms 62760 KB Output is correct
9 Correct 2349 ms 68004 KB Output is correct
10 Correct 2204 ms 63792 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 724 KB Output is correct
2 Correct 389 ms 11492 KB Output is correct
3 Correct 501 ms 11568 KB Output is correct
4 Correct 480 ms 11572 KB Output is correct
5 Correct 595 ms 11888 KB Output is correct
6 Correct 251 ms 11488 KB Output is correct
7 Correct 481 ms 11568 KB Output is correct
8 Correct 540 ms 11476 KB Output is correct
9 Correct 604 ms 11868 KB Output is correct
10 Correct 228 ms 11532 KB Output is correct
11 Correct 497 ms 11588 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2834 ms 196312 KB Output is correct
14 Correct 3774 ms 200652 KB Output is correct
15 Correct 1099 ms 215340 KB Output is correct
16 Correct 5122 ms 259436 KB Output is correct
17 Correct 3780 ms 220544 KB Output is correct
18 Correct 2247 ms 62416 KB Output is correct
19 Correct 714 ms 62760 KB Output is correct
20 Correct 2349 ms 68004 KB Output is correct
21 Correct 2204 ms 63792 KB Output is correct
22 Correct 3568 ms 222152 KB Output is correct
23 Correct 3834 ms 224984 KB Output is correct
24 Correct 4996 ms 226096 KB Output is correct
25 Correct 5122 ms 230444 KB Output is correct
26 Correct 5122 ms 226616 KB Output is correct
27 Correct 6684 ms 259068 KB Output is correct
28 Correct 1358 ms 225708 KB Output is correct
29 Correct 5099 ms 226104 KB Output is correct
30 Correct 5102 ms 225316 KB Output is correct
31 Correct 5211 ms 226116 KB Output is correct
32 Correct 2453 ms 69316 KB Output is correct
33 Correct 664 ms 63096 KB Output is correct
34 Correct 1735 ms 60076 KB Output is correct
35 Correct 1747 ms 60140 KB Output is correct
36 Correct 2122 ms 61104 KB Output is correct
37 Correct 1968 ms 61024 KB Output is correct