oj.uz

Submission #549598

# Submission time Handle Problem Language Result Execution time Memory
549598 2022-04-16T05:48:31 Z AJ00 Factories (JOI14_factories) C++14
18 / 100
 8000 ms 108232 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAXN = 500000, LOGN = 21;
vector<vector<pair<int,int>>> adj(MAXN);
int depth[MAXN],par[MAXN][LOGN];
long long int dis[MAXN];
int lca(int u, int v){
    if (depth[u] < depth[v]){
        swap(u,v);
    }
    int k = depth[u]-depth[v];
    for (int j = LOGN-1; j >= 0; j--){
        if (k & (1<<j)){
            u = par[u][j];
        }
    }
    if (u == v){
        return v;
    }
    for (int j = LOGN-1; j >= 0; j--){
        if (par[u][j] != par[v][j]){
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}
long long int Query(int S, int X[], int T, int Y[]){
    long long int ans = 1e18;
    for (int i = 0; i < S; i++){
        for (int j = 0; j < T; j++){
            int l = lca(X[i],Y[j]);
          //  cout << X[i] << " " << Y[j] << " " << dis[X[i]] << " " << dis[Y[j]] << " " << 2*dis[l] << "\n";
            ans = min(ans,dis[X[i]]+dis[Y[j]]-(2*dis[l]));
        }
    }
    return ans;
}
void dfs(int x, int p = 0, int d = 0,long long int w = 0LL){
    depth[x] = d;
    dis[x] = dis[p]+w;
    par[x][0] = p;
    for (int i = 1; i < LOGN; i++){
        par[x][i] = par[par[x][i-1]][i-1];
       // dis[x][i] = dis[x][i-1]+dis[par[x][i-1]][i-1];
    }
    for (auto ch: adj[x]){
        if (ch.first!=p){
            dfs(ch.first,x,d+1,ch.second);
        }
    }
}
void Init(int N, int A[], int B[], int D[]){
    int n  = N;
    for (int i = 0; i < n-1; i++){
        adj[A[i]].push_back({B[i],(long long int)D[i]});
        adj[B[i]].push_back({A[i],(long long int)D[i]});
    }
    dfs(0);
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12500 KB Output is correct
2 Execution timed out 8071 ms 22012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 1333 ms 90760 KB Output is correct
3 Correct 2702 ms 91352 KB Output is correct
4 Correct 883 ms 91456 KB Output is correct
5 Correct 2350 ms 108232 KB Output is correct
6 Correct 2092 ms 92764 KB Output is correct
7 Correct 3632 ms 37060 KB Output is correct
8 Correct 1039 ms 37788 KB Output is correct
9 Correct 3223 ms 39732 KB Output is correct
10 Correct 2295 ms 38152 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12500 KB Output is correct
2 Execution timed out 8071 ms 22012 KB Time limit exceeded
3 Halted 0 ms 0 KB -