oj.uz

Submission #767990

# Submission time Handle Problem Language Result Execution time Memory
767990 2023-06-27T10:47:04 Z phoenix Factories (JOI14_factories) C++17
100 / 100
 4239 ms 356136 KB 
#include<bits/stdc++.h>
// #include"factories.h"

using namespace std;

struct e {
    int to;
    long long weight;
};

const int dick = 500000 + 5;
vector<e> g[dick];

int nnnn;
int lengthOf[dick];
bool rv[dick];

// first = centroid, second = distance to centroid 
vector<pair<int, long long>> DC[dick];

int count(int s, int p = -1) {
    lengthOf[s] = 1;
    for(auto f : g[s]) {
        if(rv[f.to] || f.to == p) continue;
        lengthOf[s] += count(f.to, s);
    }
    return lengthOf[s];
}

int find_centroid(int s, int p = -1, int mn = nnnn) {
    for(auto f : g[s]) {
        if(rv[f.to] || f.to == p) continue;
        if(lengthOf[f.to] * 2 > mn) return find_centroid(f.to, s, mn);
    }   
    return s;
}
long long dist[dick];
void dfs(int s, int p, int C) {
    DC[s].push_back({C, dist[s]});
    for(auto to : g[s]) {
        if(rv[to.to] || to.to == p) continue;
        dist[to.to] = dist[s] + to.weight;
        dfs(to.to, s, C); 
    }
}
 
void decompose(int s) {
    int C = find_centroid(s, s, count(s));
    dist[C] = 0;
    dfs(C, C, C);

    rv[C] = 1;
    for(auto to : g[C]) {
        if(rv[to.to]) continue;
        decompose(to.to);
    }
}

const long long inf = 1e18;
long long queryDist[dick];
void Init(int N, int A[], int B[], int D[]) {
    nnnn = N;
    for(int i = 0; i < N - 1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    for(int i = 0; i < N; i++)
        queryDist[i] = inf;
    decompose(0);
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < T; i++) {
        int v = Y[i];
        for(auto c : DC[v]) 
            queryDist[c.first] = min(queryDist[c.first], c.second);
    }
    long long res = 1e18;
    for(int i = 0; i < S; i++) {
        int v = X[i];
        for(auto c : DC[v]) 
            res = min(res, c.second + queryDist[c.first]);
    }
    for(int i = 0; i < T; i++) {
        int v = Y[i];
        for(auto c : DC[v]) 
            queryDist[c.first] = inf;
    }
    return res;
}

// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0);cout.tie(0);
//     int n;
//     cin >> n;
//     int a[n - 1], b[n - 1]; long long d[n - 1]; 
//     for(int i = 0; i < n - 1; i++) {
//         cin >> a[i];
//         cin >> b[i];
//         cin >> d[i];
//     }
//     Init(n, a, b, d);
//     int t;
//     cin >> t;
//     while(t--) {
//         int s, t;
//         cin >> s;
//         int x[s]; 
//         for(int i = 0; i < s; i++)
//             cin >> x[i];
//         cin >> t; 
//         int y[t];
//         for(int i = 0; i < t; i++)
//             cin >> y[i];
//         cout << Query(s, x, t, y) << '\n';
//     }    
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24336 KB Output is correct
2 Correct 203 ms 42320 KB Output is correct
3 Correct 219 ms 42820 KB Output is correct
4 Correct 208 ms 42836 KB Output is correct
5 Correct 223 ms 43212 KB Output is correct
6 Correct 156 ms 41900 KB Output is correct
7 Correct 210 ms 42768 KB Output is correct
8 Correct 211 ms 42836 KB Output is correct
9 Correct 225 ms 43240 KB Output is correct
10 Correct 158 ms 41868 KB Output is correct
11 Correct 207 ms 42800 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 2058 ms 200284 KB Output is correct
3 Correct 3372 ms 270976 KB Output is correct
4 Correct 725 ms 94264 KB Output is correct
5 Correct 3898 ms 346244 KB Output is correct
6 Correct 3418 ms 289652 KB Output is correct
7 Correct 816 ms 83528 KB Output is correct
8 Correct 266 ms 60664 KB Output is correct
9 Correct 842 ms 98596 KB Output is correct
10 Correct 774 ms 85108 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24336 KB Output is correct
2 Correct 203 ms 42320 KB Output is correct
3 Correct 219 ms 42820 KB Output is correct
4 Correct 208 ms 42836 KB Output is correct
5 Correct 223 ms 43212 KB Output is correct
6 Correct 156 ms 41900 KB Output is correct
7 Correct 210 ms 42768 KB Output is correct
8 Correct 211 ms 42836 KB Output is correct
9 Correct 225 ms 43240 KB Output is correct
10 Correct 158 ms 41868 KB Output is correct
11 Correct 207 ms 42800 KB Output is correct
12 Correct 14 ms 24020 KB Output is correct
13 Correct 2058 ms 200284 KB Output is correct
14 Correct 3372 ms 270976 KB Output is correct
15 Correct 725 ms 94264 KB Output is correct
16 Correct 3898 ms 346244 KB Output is correct
17 Correct 3418 ms 289652 KB Output is correct
18 Correct 816 ms 83528 KB Output is correct
19 Correct 266 ms 60664 KB Output is correct
20 Correct 842 ms 98596 KB Output is correct
21 Correct 774 ms 85108 KB Output is correct
22 Correct 2415 ms 205744 KB Output is correct
23 Correct 2360 ms 210488 KB Output is correct
24 Correct 3583 ms 278624 KB Output is correct
25 Correct 3516 ms 282004 KB Output is correct
26 Correct 3597 ms 279284 KB Output is correct
27 Correct 4239 ms 356136 KB Output is correct
28 Correct 818 ms 104432 KB Output is correct
29 Correct 3704 ms 278704 KB Output is correct
30 Correct 3688 ms 280264 KB Output is correct
31 Correct 3534 ms 278772 KB Output is correct
32 Correct 967 ms 98812 KB Output is correct
33 Correct 253 ms 61112 KB Output is correct
34 Correct 521 ms 76032 KB Output is correct
35 Correct 519 ms 76744 KB Output is correct
36 Correct 805 ms 81912 KB Output is correct
37 Correct 762 ms 81908 KB Output is correct