oj.uz

답안 #658973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658973 2022-11-15T17:19:13 Z esomer 공장들 (JOI14_factories) C++17
100 / 100
 4987 ms 241892 KB 
#include<bits/stdc++.h>
#include "factories.h"

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;
const int maxN = 500001;
const int maxEuler = 3000000;
const int maxlog = 20;

int sparse[maxEuler][23];
int euler[maxEuler];
int lb[maxEuler];
pair<int, int> t[maxN];
ll dists[maxN];
int depths[maxN];
vector<pair<int, ll>> adj[maxN];
bool done[maxN];
int subtree_size[maxN];
int parents[maxN];
ll ans[maxN];
int centr;
int root;
int cnt;

void DFS_lca(int x, int p){
    t[x].first = cnt;
    euler[cnt] = x; cnt++;
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node != p){
            depths[node] = depths[x] + 1;
            dists[node] = dists[x] + pr.second;
            DFS_lca(node, x);
            t[x].second = cnt;
            euler[cnt] = x; cnt++;
        }
    }
    if(t[x].first + 1 == cnt){
        t[x].second = cnt;
        euler[cnt] = x; cnt++;
    }
}

void build_lca(int n){
    depths[0] = 0;
    dists[0] = 0;
    cnt = 0;
    DFS_lca(0, -1);
    for(int i = 0; i < 23; i++){
        for(int j = 0; j < cnt; j++){
            if(i > 0){
                if(depths[sparse[j][i - 1]] < depths[sparse[max(0, j - (1<<(i - 1)))][i - 1]]){
                    sparse[j][i] = sparse[j][i - 1];
                }else sparse[j][i] = sparse[max(0, j - (1<<(i - 1)))][i - 1];
            }
            else sparse[j][i] = euler[j];
        }
    }
    ll pw = 1;
    int curr = 0;
    for(int i = 1; i <= cnt; i++){
        if(i == pw * 2){
            pw *= 2; curr++;
        }
        lb[i] = curr;
    }
}

int lca(int a, int b){
    if(a == b) return a;
    int l = min(t[a].first, t[b].first); int r = max(t[a].second, t[b].second);
    int dst = r - l + 1;
    if(depths[sparse[r][lb[dst]]] < depths[sparse[l + (1 << lb[dst]) - 1][lb[dst]]]) return sparse[r][lb[dst]];
    else return sparse[l + (1 << lb[dst]) - 1][lb[dst]];
}

ll dist(int a, int b){
    int anc = lca(a, b);
    return dists[a] + dists[b] - 2 * dists[anc];
}

int find_size(int x, int par){
    subtree_size[x] = 1;
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node == par || done[node] == 1) continue;
        subtree_size[x] += find_size(node,  x);
    }
    return subtree_size[x];
}

void find_centroid(int x, int par, int siz){
    bool good = 1;
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node == par || done[node] == 1) continue;
        if(subtree_size[node] > siz / 2){
            find_centroid(node, x, siz);
            good = 0;
        }
    }
    if(good) centr = x;
}

void build(int x, int par){
    int siz = find_size(x, -1);
    centr = -1;
    find_centroid(x, -1, siz);
    parents[centr] = par;
    done[centr] = 1;
    int mine = centr;
    for(auto pr : adj[mine]){
        int node = pr.first;
        if(!done[node]) build(node, mine);
    }
}


void add(int x){
    int next = x;
    while(next != -1){
        ll d = dist(next, x);
        ans[next] = min(ans[next], d);
        next = parents[next];
    }
}

void rmv(int x){
    int next = x;
    while(next != -1){
        ans[next] = 1e18;
        next = parents[next];
    }
}

ll query(int x){
    int next = x;
    ll rep = 1e18;
    while(next != -1){
        ll d = dist(next, x);
        rep = min(rep, ans[next] + d);
        next = parents[next];
    }
    return rep;
}

void Init(int N, int A[], int B[], int D[]){
    for(int i = 0; i < N - 1; i++){
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    build_lca(N);
    build(0, -1);
    for(int i = 0; i < N; i++) ans[i] = 1e18;
}

ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++) add(X[i]);
    ll retrn = 1e18;
    for(int i = 0; i < T; i++) retrn = min(retrn, query(Y[i]));
    for(int i = 0; i < S; i++) rmv(X[i]);
    return retrn;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12756 KB Output is correct
2 Correct 388 ms 31196 KB Output is correct
3 Correct 476 ms 31208 KB Output is correct
4 Correct 424 ms 31204 KB Output is correct
5 Correct 467 ms 31476 KB Output is correct
6 Correct 221 ms 31616 KB Output is correct
7 Correct 423 ms 31280 KB Output is correct
8 Correct 456 ms 31260 KB Output is correct
9 Correct 451 ms 31292 KB Output is correct
10 Correct 219 ms 31544 KB Output is correct
11 Correct 425 ms 31228 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2233 ms 191900 KB Output is correct
3 Correct 3120 ms 204760 KB Output is correct
4 Correct 922 ms 231352 KB Output is correct
5 Correct 3963 ms 212672 KB Output is correct
6 Correct 3220 ms 206940 KB Output is correct
7 Correct 1470 ms 69140 KB Output is correct
8 Correct 376 ms 75192 KB Output is correct
9 Correct 1442 ms 69560 KB Output is correct
10 Correct 1428 ms 70512 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12756 KB Output is correct
2 Correct 388 ms 31196 KB Output is correct
3 Correct 476 ms 31208 KB Output is correct
4 Correct 424 ms 31204 KB Output is correct
5 Correct 467 ms 31476 KB Output is correct
6 Correct 221 ms 31616 KB Output is correct
7 Correct 423 ms 31280 KB Output is correct
8 Correct 456 ms 31260 KB Output is correct
9 Correct 451 ms 31292 KB Output is correct
10 Correct 219 ms 31544 KB Output is correct
11 Correct 425 ms 31228 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2233 ms 191900 KB Output is correct
14 Correct 3120 ms 204760 KB Output is correct
15 Correct 922 ms 231352 KB Output is correct
16 Correct 3963 ms 212672 KB Output is correct
17 Correct 3220 ms 206940 KB Output is correct
18 Correct 1470 ms 69140 KB Output is correct
19 Correct 376 ms 75192 KB Output is correct
20 Correct 1442 ms 69560 KB Output is correct
21 Correct 1428 ms 70512 KB Output is correct
22 Correct 2900 ms 216648 KB Output is correct
23 Correct 3012 ms 219656 KB Output is correct
24 Correct 4198 ms 213144 KB Output is correct
25 Correct 4374 ms 216948 KB Output is correct
26 Correct 4290 ms 213348 KB Output is correct
27 Correct 4987 ms 216864 KB Output is correct
28 Correct 1102 ms 241892 KB Output is correct
29 Correct 4632 ms 212768 KB Output is correct
30 Correct 4265 ms 212180 KB Output is correct
31 Correct 4324 ms 213188 KB Output is correct
32 Correct 1430 ms 70388 KB Output is correct
33 Correct 374 ms 75572 KB Output is correct
34 Correct 1004 ms 67956 KB Output is correct
35 Correct 1151 ms 67948 KB Output is correct
36 Correct 1509 ms 67532 KB Output is correct
37 Correct 1403 ms 67496 KB Output is correct