oj.uz

답안 #908173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908173 2024-01-16T09:03:51 Z typ_ik 공장들 (JOI14_factories) C++17
15 / 100
 7304 ms 524288 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std; 

const int N = 5e5 + 128;
const ll INF = 1e15 + 128;
vector < pair<int, int> > g[N];
int n, q;
bool was[N];
int h[N];
unordered_map <int, ll> d[N];
ll res[N];

void dfs(int v, int p = -1) {
    h[v] = 1;   

    for (auto& [to, len] : g[v])
        if (to != p && !was[to])
            dfs(to, v), h[v] += h[to];
}

void calc(int v, int cent, ll val, int p) {
    d[cent][v] = val;

    for (auto& [to, len] : g[v])
        if (to != p && !was[to])
            calc(to, cent, val+len, v);
}

int find_centroid(int v, int p, int sz) { 
    for (auto& [to, len] : g[v])
        if (to != p && h[to] > sz / 2 && !was[to])
            return find_centroid(to, v, sz);
    return v;
}

int p[N];

void decompose(int v, int pr = -1) { 
    dfs(v); 

    int c = find_centroid(v, -1, h[v]);  

    calc(c, c, 0, -1);

    p[c] = pr;
    was[c] = true;

    for (auto& [to, len] : g[c])
        if (!was[to])
            decompose(to, c);
}

void update(int v) {
    int c = v;
    while (c != -1) 
        res[c] = min(res[c], d[c][v]), c = p[c];
}

void reset(int v) {
    int c = v;
    while (c != -1) 
        res[c] = INF, c = p[c]; 
}

ll get(int v) {
    ll ans = INF;
    int c = v;
    while (c != -1)
        ans = min(ans, d[c][v]+res[c]), c = p[c];
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i + 1 < n; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    for (int i = 0; i <= n; i++)
        res[i] = INF, p[i] = -1;
    decompose(1);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        update(X[i]);
    ll tot = INF;
    for (int i = 0; i < T; i++)
        tot = min(tot, get(Y[i]));
    for (int i = 0; i < S; i++)
        reset(X[i]);
    return tot;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 62288 KB Output is correct
2 Correct 448 ms 73204 KB Output is correct
3 Correct 558 ms 73856 KB Output is correct
4 Correct 531 ms 73684 KB Output is correct
5 Correct 642 ms 74448 KB Output is correct
6 Correct 216 ms 72364 KB Output is correct
7 Correct 542 ms 73552 KB Output is correct
8 Correct 561 ms 73684 KB Output is correct
9 Correct 643 ms 74180 KB Output is correct
10 Correct 224 ms 72016 KB Output is correct
11 Correct 557 ms 73556 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 62044 KB Output is correct
2 Correct 5094 ms 361888 KB Output is correct
3 Correct 7304 ms 484452 KB Output is correct
4 Correct 1226 ms 200624 KB Output is correct
5 Runtime error 3989 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 62288 KB Output is correct
2 Correct 448 ms 73204 KB Output is correct
3 Correct 558 ms 73856 KB Output is correct
4 Correct 531 ms 73684 KB Output is correct
5 Correct 642 ms 74448 KB Output is correct
6 Correct 216 ms 72364 KB Output is correct
7 Correct 542 ms 73552 KB Output is correct
8 Correct 561 ms 73684 KB Output is correct
9 Correct 643 ms 74180 KB Output is correct
10 Correct 224 ms 72016 KB Output is correct
11 Correct 557 ms 73556 KB Output is correct
12 Correct 19 ms 62044 KB Output is correct
13 Correct 5094 ms 361888 KB Output is correct
14 Correct 7304 ms 484452 KB Output is correct
15 Correct 1226 ms 200624 KB Output is correct
16 Runtime error 3989 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -