oj.uz

Submission #658750

# Submission time Handle Problem Language Result Execution time Memory
658750 2022-11-14T20:06:44 Z esomer Factories (JOI14_factories) C++17
15 / 100
 8000 ms 149992 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 maxlog = 20;

int dp[maxN][maxlog];
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;

void DFS_lca(int x, int p){
    dp[x][0] = p;
    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);
        }
    }
}

void build_lca(int n){
    depths[0] = 0;
    DFS_lca(0, -1);
    for(int i = 1; i < 20; i++){
        for(int j = 0; j < n; j++){
            if(dp[j][i - 1] == -1) {dp[j][i] = -1; continue;}
            dp[j][i] = dp[dp[j][i - 1]][i - 1];
        }
    }
}

int kth(int x, int d){
    for(int k = 19; k >= 0; k--){
        if((1 << k) <= d){
            x = dp[x][k];
            d -= (1 << k);
        }
    }
    return x;
}

int lca(int a, int b){
    if(depths[b] > depths[a]) b = kth(b, depths[b] - depths[a]);
    else if(depths[a] > depths[b]) a = kth(a, depths[a] - depths[b]);
    if(a == b) return a;
    int anc = -1;
    for(int k = 19; k >= 0; k--){
        if(dp[a][k] == dp[b][k]){
            anc = max(0, dp[a][k]);
        }else{
            a = dp[a][k];
            b = dp[b][k];
        }
    }
    return anc;
}

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 n){
    queue<pair<int, int>> q;
    q.push({0, -1});
    while(!q.empty()){
        int x = q.front().first; int par = q.front().second; q.pop();
        int siz = find_size(x, -1);
        centr = -1;
        find_centroid(x, -1, siz);
        if(par == -1) root = centr;
        parents[centr] = par;
        done[centr] = 1;
        for(auto pr : adj[centr]){
            int node = pr.first;
            if(!done[node]) q.push({node, centr});
        }
    }
}

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(N);
    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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12500 KB Output is correct
2 Correct 734 ms 21008 KB Output is correct
3 Correct 1293 ms 21288 KB Output is correct
4 Correct 1289 ms 30508 KB Output is correct
5 Correct 1515 ms 30648 KB Output is correct
6 Correct 272 ms 30452 KB Output is correct
7 Correct 1303 ms 30384 KB Output is correct
8 Correct 1363 ms 30372 KB Output is correct
9 Correct 1485 ms 30636 KB Output is correct
10 Correct 241 ms 30340 KB Output is correct
11 Correct 1339 ms 30636 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 2754 ms 104780 KB Output is correct
3 Correct 6050 ms 107964 KB Output is correct
4 Correct 736 ms 123796 KB Output is correct
5 Execution timed out 8039 ms 149992 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12500 KB Output is correct
2 Correct 734 ms 21008 KB Output is correct
3 Correct 1293 ms 21288 KB Output is correct
4 Correct 1289 ms 30508 KB Output is correct
5 Correct 1515 ms 30648 KB Output is correct
6 Correct 272 ms 30452 KB Output is correct
7 Correct 1303 ms 30384 KB Output is correct
8 Correct 1363 ms 30372 KB Output is correct
9 Correct 1485 ms 30636 KB Output is correct
10 Correct 241 ms 30340 KB Output is correct
11 Correct 1339 ms 30636 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 2754 ms 104780 KB Output is correct
14 Correct 6050 ms 107964 KB Output is correct
15 Correct 736 ms 123796 KB Output is correct
16 Execution timed out 8039 ms 149992 KB Time limit exceeded
17 Halted 0 ms 0 KB -