oj.uz

Submission #959622

# Submission time Handle Problem Language Result Execution time Memory
959622 2024-04-08T14:04:29 Z dong_gas Factories (JOI14_factories) C++17
100 / 100
 3140 ms 197016 KB 
#include <bits/extc++.h>
#include "factories.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, q;
int sz[500050], use[500050], cent_papa[500050], dep[500050];
vector<pint> adj[500050];
ll m[500050], lv_dist[500050][23];

int get_size(int u, int p=0) {
    sz[u]=1;
    for(auto& [v, w]:adj[u]) {
        if(use[v] || p==v) continue;
        sz[u]+=get_size(v,u);
    }
    return sz[u];
}

int get_cent(int u, int p, int cnt) {
    for(auto& [v, w]:adj[u]) {
        if(use[v] || v==p) continue;
        if(sz[v]>cnt/2) return get_cent(v,u,cnt);
    }
    return u;
}

void go(int u, int p, int lv) {
    for(auto& [v,w]:adj[u]) {
        if(use[v] || v==p) continue;
        lv_dist[v][lv]=lv_dist[u][lv]+w;
        go(v,u,lv);
    }
}

void dnc(int u, int p=0, int lv=0) {//p는 이전 cent
    int cent=get_cent(u,p,get_size(u,p));
    cent_papa[cent]=p;
    use[cent]=1;
    dep[cent]=lv;
    go(cent, 0, lv);
    for(auto& [v, w]:adj[cent]) if(!use[v]) dnc(v,cent,lv+1);
}

void update(int u) {
    int now=u;
    do {        
        m[now]=min(m[now],lv_dist[u][dep[now]]);
        now=cent_papa[now];
    } while(now);    
}

void downdate(int u) {
    int now=u;
    do {
        m[now]=1e18;
        now=cent_papa[now];
    } while(now);    
}

ll query(int u) {
    int now=u;
    ll ret=1e18;
    do {        
        ret=min(ret, m[now] + lv_dist[u][dep[now]]);
        now=cent_papa[now];        
    } while(now);
    return (ret<1e18) ? ret : -1;
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<n-1;i++) {
        adj[A[i]+1].emplace_back(B[i]+1,D[i]);
        adj[B[i]+1].emplace_back(A[i]+1,D[i]);
    }
    dnc(1);
    fill(m+1,m+n+1,1e18);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ret=1e18;
    for(int i=0;i<S;i++) update(X[i]+1);
    for(int i=0;i<T;i++) ret=min(ret,query(Y[i]+1));
    for(int i=0;i<S;i++) downdate(X[i]+1);
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39516 KB Output is correct
2 Correct 204 ms 54104 KB Output is correct
3 Correct 239 ms 54096 KB Output is correct
4 Correct 227 ms 54096 KB Output is correct
5 Correct 258 ms 54348 KB Output is correct
6 Correct 149 ms 54092 KB Output is correct
7 Correct 231 ms 54348 KB Output is correct
8 Correct 235 ms 54104 KB Output is correct
9 Correct 254 ms 54332 KB Output is correct
10 Correct 148 ms 54096 KB Output is correct
11 Correct 233 ms 53968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 39516 KB Output is correct
2 Correct 1346 ms 172572 KB Output is correct
3 Correct 2097 ms 174436 KB Output is correct
4 Correct 464 ms 172728 KB Output is correct
5 Correct 2908 ms 196524 KB Output is correct
6 Correct 2152 ms 175468 KB Output is correct
7 Correct 564 ms 83252 KB Output is correct
8 Correct 246 ms 83136 KB Output is correct
9 Correct 689 ms 86680 KB Output is correct
10 Correct 587 ms 83876 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39516 KB Output is correct
2 Correct 204 ms 54104 KB Output is correct
3 Correct 239 ms 54096 KB Output is correct
4 Correct 227 ms 54096 KB Output is correct
5 Correct 258 ms 54348 KB Output is correct
6 Correct 149 ms 54092 KB Output is correct
7 Correct 231 ms 54348 KB Output is correct
8 Correct 235 ms 54104 KB Output is correct
9 Correct 254 ms 54332 KB Output is correct
10 Correct 148 ms 54096 KB Output is correct
11 Correct 233 ms 53968 KB Output is correct
12 Correct 7 ms 39516 KB Output is correct
13 Correct 1346 ms 172572 KB Output is correct
14 Correct 2097 ms 174436 KB Output is correct
15 Correct 464 ms 172728 KB Output is correct
16 Correct 2908 ms 196524 KB Output is correct
17 Correct 2152 ms 175468 KB Output is correct
18 Correct 564 ms 83252 KB Output is correct
19 Correct 246 ms 83136 KB Output is correct
20 Correct 689 ms 86680 KB Output is correct
21 Correct 587 ms 83876 KB Output is correct
22 Correct 1432 ms 177328 KB Output is correct
23 Correct 1587 ms 178608 KB Output is correct
24 Correct 2485 ms 179260 KB Output is correct
25 Correct 2570 ms 181732 KB Output is correct
26 Correct 2326 ms 179708 KB Output is correct
27 Correct 3140 ms 197016 KB Output is correct
28 Correct 559 ms 179488 KB Output is correct
29 Correct 2431 ms 179348 KB Output is correct
30 Correct 2396 ms 178972 KB Output is correct
31 Correct 2397 ms 179616 KB Output is correct
32 Correct 729 ms 87080 KB Output is correct
33 Correct 270 ms 83260 KB Output is correct
34 Correct 456 ms 81364 KB Output is correct
35 Correct 487 ms 81768 KB Output is correct
36 Correct 604 ms 82364 KB Output is correct
37 Correct 618 ms 82356 KB Output is correct