oj.uz

Submission #433407

# Submission time Handle Problem Language Result Execution time Memory
433407 2021-06-19T17:40:15 Z jovan_b Factories (JOI14_factories) C++17
33 / 100
 8000 ms 363780 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) break;
        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 23 ms 24140 KB Output is correct
2 Correct 383 ms 32968 KB Output is correct
3 Correct 380 ms 33312 KB Output is correct
4 Correct 383 ms 33408 KB Output is correct
5 Correct 399 ms 33740 KB Output is correct
6 Correct 360 ms 32300 KB Output is correct
7 Correct 377 ms 33344 KB Output is correct
8 Correct 417 ms 33456 KB Output is correct
9 Correct 395 ms 33788 KB Output is correct
10 Correct 291 ms 32336 KB Output is correct
11 Correct 405 ms 33268 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24012 KB Output is correct
2 Correct 4091 ms 193488 KB Output is correct
3 Correct 6050 ms 278328 KB Output is correct
4 Correct 1239 ms 85980 KB Output is correct
5 Correct 7867 ms 363780 KB Output is correct
6 Correct 6296 ms 278740 KB Output is correct
7 Correct 1665 ms 67884 KB Output is correct
8 Correct 733 ms 45176 KB Output is correct
9 Correct 1893 ms 81280 KB Output is correct
10 Correct 1645 ms 69000 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24140 KB Output is correct
2 Correct 383 ms 32968 KB Output is correct
3 Correct 380 ms 33312 KB Output is correct
4 Correct 383 ms 33408 KB Output is correct
5 Correct 399 ms 33740 KB Output is correct
6 Correct 360 ms 32300 KB Output is correct
7 Correct 377 ms 33344 KB Output is correct
8 Correct 417 ms 33456 KB Output is correct
9 Correct 395 ms 33788 KB Output is correct
10 Correct 291 ms 32336 KB Output is correct
11 Correct 405 ms 33268 KB Output is correct
12 Correct 17 ms 24012 KB Output is correct
13 Correct 4091 ms 193488 KB Output is correct
14 Correct 6050 ms 278328 KB Output is correct
15 Correct 1239 ms 85980 KB Output is correct
16 Correct 7867 ms 363780 KB Output is correct
17 Correct 6296 ms 278740 KB Output is correct
18 Correct 1665 ms 67884 KB Output is correct
19 Correct 733 ms 45176 KB Output is correct
20 Correct 1893 ms 81280 KB Output is correct
21 Correct 1645 ms 69000 KB Output is correct
22 Correct 4701 ms 193476 KB Output is correct
23 Correct 4874 ms 197344 KB Output is correct
24 Correct 6959 ms 279312 KB Output is correct
25 Correct 6914 ms 283368 KB Output is correct
26 Correct 6793 ms 280340 KB Output is correct
27 Execution timed out 8109 ms 358420 KB Time limit exceeded
28 Halted 0 ms 0 KB -