oj.uz

Submission #433405

# Submission time Handle Problem Language Result Execution time Memory
433405 2021-06-19T17:34:51 Z jovan_b Factories (JOI14_factories) C++17
33 / 100
 8000 ms 363664 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1000000000000000000LL;

const int MAXN = 500000;

vector <pair <int, int>> graf[MAXN+5];
vector <pair <int, ll>> parents[MAXN+5];

bool erased[MAXN+5];
int sz[MAXN+5];
ll mnd[MAXN+5];

void dfs_size(int v, int p){
    sz[v] = 1;
    for(auto c : graf[v]){
        if(erased[c.first] || c.first == p) continue;
        dfs_size(c.first, v);
        sz[v] += sz[c.first];
    }
}

int find_centroid(int v, int p, int svi){
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p && 2*sz[c.first] > svi) return find_centroid(c.first, v, svi);
    return v;
}

void dfs_depth(int v, int p, ll dst, int root){
    parents[v].push_back({root, dst});
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p) dfs_depth(c.first, v, dst + c.second, root);
}

void decompose(){
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        dfs_size(v, 0);
        v = find_centroid(v, 0, sz[v]);
        dfs_depth(v, 0, 0, v);
        erased[v] = 1;
        for(auto c : graf[v]) if(!erased[c.first]) q.push(c.first);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N-1; i++){
        A[i]++;
        B[i]++;
        graf[A[i]].push_back({B[i], D[i]});
        graf[B[i]].push_back({A[i], D[i]});
    }
    decompose();
    for(int i=1; i<=N; i++) reverse(parents[i].begin(), parents[i].end());
    for(int i=1; i<=N; i++) mnd[i] = INF;
}

void upd(int x){
    for(auto c : parents[x]) mnd[c.first] = min(mnd[c.first], c.second);
}

void brisi(int x){
    for(auto c : parents[x]){
        if(mnd[c.first] == INF) continue;
        mnd[c.first] = INF;
    }
}

ll query(int x){
    ll res = INF;
    for(auto c : parents[x]) res = min(res, c.second + mnd[c.first]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn = INF;
    for(int i=0; i<S; i++) upd(X[i]+1);
    for(int i=0; i<T; i++) mn = min(mn, query(Y[i]+1));
    for(int i=0; i<S; i++) brisi(X[i]+1);
    return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24388 KB Output is correct
2 Correct 371 ms 42412 KB Output is correct
3 Correct 399 ms 42804 KB Output is correct
4 Correct 408 ms 42852 KB Output is correct
5 Correct 431 ms 43248 KB Output is correct
6 Correct 341 ms 41848 KB Output is correct
7 Correct 406 ms 42900 KB Output is correct
8 Correct 408 ms 42936 KB Output is correct
9 Correct 430 ms 43184 KB Output is correct
10 Correct 296 ms 41796 KB Output is correct
11 Correct 402 ms 43080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 3992 ms 194032 KB Output is correct
3 Correct 5918 ms 278736 KB Output is correct
4 Correct 1122 ms 85896 KB Output is correct
5 Correct 7516 ms 363664 KB Output is correct
6 Correct 6012 ms 278752 KB Output is correct
7 Correct 1543 ms 68404 KB Output is correct
8 Correct 567 ms 45908 KB Output is correct
9 Correct 1804 ms 82016 KB Output is correct
10 Correct 1538 ms 69620 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24388 KB Output is correct
2 Correct 371 ms 42412 KB Output is correct
3 Correct 399 ms 42804 KB Output is correct
4 Correct 408 ms 42852 KB Output is correct
5 Correct 431 ms 43248 KB Output is correct
6 Correct 341 ms 41848 KB Output is correct
7 Correct 406 ms 42900 KB Output is correct
8 Correct 408 ms 42936 KB Output is correct
9 Correct 430 ms 43184 KB Output is correct
10 Correct 296 ms 41796 KB Output is correct
11 Correct 402 ms 43080 KB Output is correct
12 Correct 18 ms 24012 KB Output is correct
13 Correct 3992 ms 194032 KB Output is correct
14 Correct 5918 ms 278736 KB Output is correct
15 Correct 1122 ms 85896 KB Output is correct
16 Correct 7516 ms 363664 KB Output is correct
17 Correct 6012 ms 278752 KB Output is correct
18 Correct 1543 ms 68404 KB Output is correct
19 Correct 567 ms 45908 KB Output is correct
20 Correct 1804 ms 82016 KB Output is correct
21 Correct 1538 ms 69620 KB Output is correct
22 Correct 4549 ms 193760 KB Output is correct
23 Correct 4673 ms 197624 KB Output is correct
24 Correct 6867 ms 279324 KB Output is correct
25 Correct 6879 ms 283324 KB Output is correct
26 Correct 6723 ms 280496 KB Output is correct
27 Execution timed out 8064 ms 358888 KB Time limit exceeded
28 Halted 0 ms 0 KB -