oj.uz

답안 #853741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853741 2023-09-25T07:29:18 Z anha3k25cvp 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 122756 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "factories.h"

using namespace std;

const ll inf = 7 + 1e18;

int n, logn, tsize;
vector <int> sz, pa, h;
vector <ll> f;
vector <vector <int>> p;
vector <vector <II>> adj;

///--------------------------LCA-------------------------------

void dfs_lca(int u) {
    for (auto z : adj[u]) {
        int v = z.st;
        ll w = z.nd;
        if (h[v])
            continue;
        h[v] = h[u] + 1;
        f[v] = f[u] + w;
        p[0][v] = u;
        dfs_lca(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v])
        swap(u, v);
    int d = h[u] - h[v];
    for (int si = d; si > 0; si ^= si & -si) {
        int i = __builtin_ctz(si & -si);
        u = p[i][u];
    }
    if (u == v)
        return u;
    for (int i = logn - 1; i >= 0; i --)
        if (p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    return p[0][u];
}

ll dis(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}

///-------------------------CENTROID-----------------------------

void dfs(int u, int p) {
    tsize ++;
    sz[u] = 1;
    for (auto z : adj[u]) {
        int v = z.st;
        if (v == p || pa[v])
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p) {
    for (auto z : adj[u]) {
        int v = z.st;
        if (v == p || pa[v])
            continue;
        if (sz[v] * 2 > tsize)
            return centroid(v, u);
    }
    return u;
}

void build(int u, int p) {
    tsize = 0;
    dfs(u, 0);
    int c = centroid(u, 0);
    if (p == 0)
        pa[c] = c;
    else
        pa[c] = p;
    for (auto z : adj[c]) {
        int v = z.st;
        if (pa[v])
            continue;
        build(v, c);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    adj.resize(n + 1);
    for (int i = 0; i < n - 1; i ++) {
        A[i] ++; B[i] ++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    for (logn = 1; (1 << logn) <= n; logn ++);
    h.assign(n + 1, 0);
    p.assign(logn, vector <int> (n + 1, 0));
    f.assign(n + 1, 0);
    h[1] = 1;
    dfs_lca(1);
    for (int i = 1; i < logn; i ++)
        for (int u = 1; u <= n; u ++)
            p[i][u] = p[i - 1][p[i - 1][u]];
    sz.assign(n + 1, 0);
    pa.assign(n + 1, 0);
    build(1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector <ll> ans(n + 1, inf);
    for (int i = 0; i < S; i ++) {
        int u = X[i] + 1;
        ans[u] = 0;
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            ans[v] = min(ans[v], dis(v, u));
        }
    }
    ll res = inf;
    for (int i = 0; i < T; i ++) {
        int u = Y[i] + 1;
        res = min(res, ans[u]);
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            res = min(res, dis(v, u) + ans[v]);
        }
    }
    return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 16732 KB Output is correct
2 Correct 323 ms 31092 KB Output is correct
3 Correct 639 ms 31016 KB Output is correct
4 Correct 590 ms 31020 KB Output is correct
5 Correct 578 ms 31312 KB Output is correct
6 Correct 158 ms 31020 KB Output is correct
7 Correct 625 ms 31152 KB Output is correct
8 Correct 640 ms 31384 KB Output is correct
9 Correct 580 ms 31324 KB Output is correct
10 Correct 154 ms 31148 KB Output is correct
11 Correct 626 ms 31008 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Execution timed out 8013 ms 122756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 16732 KB Output is correct
2 Correct 323 ms 31092 KB Output is correct
3 Correct 639 ms 31016 KB Output is correct
4 Correct 590 ms 31020 KB Output is correct
5 Correct 578 ms 31312 KB Output is correct
6 Correct 158 ms 31020 KB Output is correct
7 Correct 625 ms 31152 KB Output is correct
8 Correct 640 ms 31384 KB Output is correct
9 Correct 580 ms 31324 KB Output is correct
10 Correct 154 ms 31148 KB Output is correct
11 Correct 626 ms 31008 KB Output is correct
12 Correct 3 ms 16728 KB Output is correct
13 Execution timed out 8013 ms 122756 KB Time limit exceeded
14 Halted 0 ms 0 KB -