oj.uz

Submission #821148

# Submission time Handle Problem Language Result Execution time Memory
821148 2023-08-11T07:47:21 Z Alihan_8 Factories (JOI14_factories) C++17
0 / 100
 8000 ms 88480 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

const long long inf = 1e15 + 1;

const int N = 5e5 + 1;

vector <pair<int,int>> g[N];

int n, up[N][20], d[N];

long long dis[N];

void dfs(int x, int par){
    up[x][0] = par;
    for ( int i = 1; i < 20; i++ ){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for ( auto [to, w]: g[x] ){
        if ( to != par ){
            dis[to] = dis[x] + w;
            d[to] = d[x] + 1;
            dfs(to, x);
        }
    }
}

int lca(int x, int y){
    if ( d[x] < d[y] ) swap(x, y);
    int dif = d[x] - d[y];
    for ( int i = 0; i < 20; i++ ){
        if ( dif >> i & 1 ){
            x = up[x][i];
        }
    }
    if ( x == y ){
        return x;
    }
    for ( int i = 19; i >= 0; i-- ){
        if ( up[x][i] != up[y][i] ){
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

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

long long Query(int S, int X[], int T, int Y[]) {
    auto get = [&](int u, int v){
        return dis[u] + dis[v] - dis[lca(u, v)] * 2;
    };
    long long ans = inf;
    for ( int i = 0; i < S; i++ ){
        for ( int j = 0; j < T; j++ ){
            chmin(ans, get(X[i], Y[j]));
        }
    }
    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12400 KB Output is correct
2 Execution timed out 8076 ms 20648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Incorrect 1220 ms 88480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12400 KB Output is correct
2 Execution timed out 8076 ms 20648 KB Time limit exceeded
3 Halted 0 ms 0 KB -