oj.uz

답안 #906102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906102 2024-01-13T13:57:56 Z a_l_i_r_e_z_a 공장들 (JOI14_factories) C++17
15 / 100
 231 ms 79792 KB 
// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 2e5 + 5;
const ll inf = 1e18 + 7;
int n, q, sz[maxn];
ll dist[maxn];
vector<pll> adj[maxn];
vector<pll> par[maxn];
bool mark[maxn];

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

int find(int v, int s, int p = -1){
    for(auto [u, w]: adj[v]) if(u != p && !mark[u] && sz[u] * 2 > s) return find(u, s, v);
    return v;
}

void dfs(int v, int center, ll h = 0, int p = -1){
    par[v].pb(mp(center, h));
    for(auto [u, w]: adj[v]){
        if(!mark[u] && u != p) dfs(u, center, h +  w, v);
    }
}

void centroid_decomp(int v = 0){
    get_sz(v);
    v = find(v, sz[v]);
    dfs(v, v);
    mark[v] = 1;
    for(auto [u, w]: adj[v]) if(!mark[u]) centroid_decomp(u);
}

void turnOff(int v){
    for(auto [p, d]: par[v]) dist[p] = inf;
}

void turnOn(int v){
    for(auto [p, d]: par[v]) smin(dist[p], d);
}

ll get(int v){
    ll res = inf;
    for(auto [p, d]: par[v]) smin(res, d + dist[p]);
    return res;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    fill(dist, dist + n, inf);
    for(int i = 0; i < n - 1; i++){
        int u = A[i], v = B[i], w = D[i];
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    centroid_decomp();
}

ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++) turnOn(X[i]);
    ll ans = inf;
    for(int i = 0; i < T; i++) smin(ans, get(Y[i]));
    for(int i = 0; i < S; i++) turnOff(X[i]);
    return ans;
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, q; cin >> n >> q;
//     fill(dist, dist + n, inf);
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         adj[u].pb(mp(v, w));
//         adj[v].pb(mp(u, w));
//     }
//     centroid_decomp();
//     while(q--){
//         int S, T; cin >> S >> T;
//         for(int i = 0; i < S; i++){
//             cin >> a[i];
//             turnOn(a[i]);
//         }
//         ll ans = inf;
//         for(int i = 0; i < T; i++){
//             int v; cin >> v;
//             smin(ans, get(v));
//         }
//         for(int i = 0; i < S; i++) turnOff(a[i]);
//         cout << ans << '\n';
//     }

//     return 0;
// }

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 31320 KB Output is correct
2 Correct 203 ms 41688 KB Output is correct
3 Correct 208 ms 39632 KB Output is correct
4 Correct 210 ms 39632 KB Output is correct
5 Correct 214 ms 40016 KB Output is correct
6 Correct 147 ms 38480 KB Output is correct
7 Correct 225 ms 39520 KB Output is correct
8 Correct 212 ms 39620 KB Output is correct
9 Correct 214 ms 39892 KB Output is correct
10 Correct 155 ms 38688 KB Output is correct
11 Correct 204 ms 39760 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 31320 KB Output is correct
2 Runtime error 231 ms 79792 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 31320 KB Output is correct
2 Correct 203 ms 41688 KB Output is correct
3 Correct 208 ms 39632 KB Output is correct
4 Correct 210 ms 39632 KB Output is correct
5 Correct 214 ms 40016 KB Output is correct
6 Correct 147 ms 38480 KB Output is correct
7 Correct 225 ms 39520 KB Output is correct
8 Correct 212 ms 39620 KB Output is correct
9 Correct 214 ms 39892 KB Output is correct
10 Correct 155 ms 38688 KB Output is correct
11 Correct 204 ms 39760 KB Output is correct
12 Correct 9 ms 31320 KB Output is correct
13 Runtime error 231 ms 79792 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -