oj.uz

Submission #976308

# Submission time Handle Problem Language Result Execution time Memory
976308 2024-05-06T12:13:52 Z saayan007 Factories (JOI14_factories) C++17
18 / 100
 8000 ms 232932 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const char nl = '\n';

using ll = long long;
/* #warning checkconstanst as per subtask */
const int mxN = 5e5L + 10;
const int logN = 20;
vector<pair<int, ll>> adj[mxN];
int n;
int par[mxN][logN + 1], dep[mxN];
ll dist[mxN][logN + 1];

void dfs(int x, int p) {
    for(auto U : adj[x]) {
        int y = U.first; ll w = U.second;
        if(y == p) continue;
        dep[y] = dep[x] + 1;
        dist[y][0] = w;
        par[y][0] = x;
        dfs(y, x);
    }
}

/* void Init(int N, int A[], int B[], int D[]) { */
void Init(signed N, signed A[], signed B[], signed D[]) {
    n = N;
    for(int i = 0; i < N - 1; ++i) {
        adj[A[i]].emplace_back(B[i], ll(D[i]));
        adj[B[i]].emplace_back(A[i], ll(D[i]));
    }

    dep[0] = 0;
    dist[0][0] = -1;
    par[0][0] = -1;
    dfs(0, -1);
    for(int j = 1; j < logN; ++j) {
        for(int i = 0; i < N; ++i) {
            if(dep[i] < (1ll << j)) {
                par[i][j] = dist[i][j] = -1;
            }
            else {
                par[i][j] = par[par[i][j - 1]][j - 1];
                dist[i][j] = dist[i][j - 1] + dist[par[i][j - 1]][j - 1];
            }
        }
    }
}

ll distance(int x, int y) {
    ll res = 0;
    if(dep[x] < dep[y]) swap(x, y);
    ll diff = dep[x] - dep[y];
    for(int j = logN - 1; j >= 0; --j) {
        if(diff < (1ll << j)) continue;
        diff -= (1ll << j);
        res += dist[x][j];
        x = par[x][j];
    }

    if(x == y) return res;

    for(int j = logN - 1; j >= 0; --j) {
        if(par[x][j] == par[y][j]) continue;
        res += dist[x][j];
        x = par[x][j];
        res += dist[y][j];
        y = par[y][j];
    }
    res += dist[x][0];
    x = par[x][0];
    res += dist[y][0];
    y = par[y][0];
    assert(x == y);
    return res;
}

long long Query(signed S, signed X[], signed T, signed Y[]) {
    ll res = 1e18;
    for(int i = 0; i < S; ++i) {
        int x = X[i];
        for(int j = 0; j < T; ++j) {
            int y = Y[j];
            res = min(res, distance(x, y));
        }
    }
    return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 37464 KB Output is correct
2 Execution timed out 8093 ms 43748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35416 KB Output is correct
2 Correct 1274 ms 186312 KB Output is correct
3 Correct 2894 ms 208472 KB Output is correct
4 Correct 809 ms 202492 KB Output is correct
5 Correct 2936 ms 232932 KB Output is correct
6 Correct 2136 ms 209184 KB Output is correct
7 Correct 3625 ms 84536 KB Output is correct
8 Correct 869 ms 83612 KB Output is correct
9 Correct 4175 ms 87712 KB Output is correct
10 Correct 2307 ms 85140 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 37464 KB Output is correct
2 Execution timed out 8093 ms 43748 KB Time limit exceeded
3 Halted 0 ms 0 KB -