oj.uz

답안 #993826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993826 2024-06-06T13:20:01 Z Albertstein 공장들 (JOI14_factories) C++17
0 / 100
 1446 ms 193508 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;

const long long maxn = 500001, INF = LLONG_MAX / 3;
bool rem[maxn];
int sub_sz[maxn];
long long mini[maxn];
vector <pair<int, long long> > Dist[maxn];
vector <pii > G [maxn];

int dfs(int u, int p = -1){
    sub_sz[u] = 1;
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            sub_sz[u] += dfs(v, u);
        }
    }
    return sub_sz[u];
}

void dfs2(int u, int p, long long dist, int r){
    Dist[u].push_back({r, dist});
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            dfs2(v, u, dist + d, r);
        }
    }
}

int g_cen(int u, int sz, int p = -1){
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            if(sub_sz[v] * 2 > sz){
                return g_cen(v, sz, u);
            }
        }
    }
    return u;
}

int sol(int r = 0){
    int sz = dfs(r);
    int c = g_cen(r, sz);
    dfs2(c, -1, 0, c);
    rem[c] = 1;
    for(auto [v, d] : G[c]){
        if(!rem[v]){
            sol(v);
        }
    }
    return c;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++){
        int a = A[i], b = B[i], d = D[i];
        G[a].push_back({b, d});
        G[b].push_back({a, d});
    }
    for(int i = 0; i < N - 1; i++) {mini[i] = INF;}
    sol();
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = INF;
    vector <int> q;
    for(int i = 0; i < S; i++){
        int x = X[i];
        for(auto [v, d] : Dist[x]){
            mini[v] = min(mini[v], d);
            q.push_back(v);
        }
    }
    for(int i = 0; i < T; i++){
        int y = Y[i];
        for(auto [v, d] : Dist[y]){
            ans = min(ans, mini[v] + d);
        }
    }//*/
    for(auto x : q) {mini[x] = INF;}
    return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 25436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25436 KB Output is correct
2 Incorrect 1446 ms 193508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 25436 KB Output isn't correct
2 Halted 0 ms 0 KB -