oj.uz

답안 #1084140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1084140 2024-09-05T10:54:10 Z f0rizen 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 146752 KB 
#include "factories.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

struct Edge {
    int to, w;
};

int n;
vector<vector<Edge>> g;
vector<bool> used;
vector<int> sz, par;
vector<vector<ll>> dist;

void dfs_sz(int v, int p = -1) {
    sz[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

void dfs_dist(int v, int p = -1, ll d = 0) {
    dist[v].push_back(d);
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs_dist(u, v, d + w);
        }
    }
}

int centroid(int v, int p, int n) {
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            if (sz[u] * 2 > n) {
                return centroid(u, v, n);
            }
        }
    }
    return v;
}

void build(int v, int p = -1) {
    dfs_sz(v);
    dfs_dist(v);
    par[v] = p;
    used[v] = 1;
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            build(centroid(u, v, sz[u]), v);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    g.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    used.resize(N);
    sz.resize(N);
    par.resize(N);
    dist.resize(N);
    dfs_sz(0);
    build(centroid(0, -1, sz[0]));
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<ll> closest(n, infll);
    for (int i = 0; i < S; ++i) {
        int v = X[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            closest[u] = min(closest[u], dist[v][j]);
            u = par[u];
            --j;
        }
    }
    ll ans = infll;
    for (int i = 0; i < T; ++i) {
        int v = Y[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            ans = min(ans, closest[u] + dist[v][j]);
            u = par[u];
            --j;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 856 KB Output is correct
2 Correct 192 ms 18752 KB Output is correct
3 Correct 198 ms 19028 KB Output is correct
4 Correct 200 ms 19024 KB Output is correct
5 Correct 218 ms 19380 KB Output is correct
6 Correct 147 ms 18532 KB Output is correct
7 Correct 195 ms 19136 KB Output is correct
8 Correct 194 ms 19104 KB Output is correct
9 Correct 224 ms 19280 KB Output is correct
10 Correct 138 ms 18392 KB Output is correct
11 Correct 199 ms 19120 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 856 KB Output is correct
2 Correct 192 ms 18752 KB Output is correct
3 Correct 198 ms 19028 KB Output is correct
4 Correct 200 ms 19024 KB Output is correct
5 Correct 218 ms 19380 KB Output is correct
6 Correct 147 ms 18532 KB Output is correct
7 Correct 195 ms 19136 KB Output is correct
8 Correct 194 ms 19104 KB Output is correct
9 Correct 224 ms 19280 KB Output is correct
10 Correct 138 ms 18392 KB Output is correct
11 Correct 199 ms 19120 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Execution timed out 8037 ms 146752 KB Time limit exceeded
14 Halted 0 ms 0 KB -