oj.uz

Submission #930897

# Submission time Handle Problem Language Result Execution time Memory
930897 2024-02-20T15:46:25 Z parlimoos Factories (JOI14_factories) C++14
100 / 100
 6385 ms 156956 KB 
//Be Name KHODA
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

const ll INF = (1ll * 1e18);

int n;
vector<arr(2)> tr[500000];
int p[500000] , id[500000] , r[500000] , cmp[500000];
ll h[500000] , seg[2][2000001];
int seginf[2000001][2] , is[500000];
int bck[30000000][2] , bckcnt = 0;

void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r , seg[0][i] = INF , seg[1][i] = INF;
    if(r > l){
        int c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
    }else is[l] = i;
}
void updF(int l , int r , int i , ll val){
    if(seginf[i][0] >= l and seginf[i][1] <= r) seg[0][i] = min(seg[0][i] , val) , bck[bckcnt][0] = 0 , bck[bckcnt++][1] = i;
    else if(seginf[i][1] >= l and seginf[i][0] <= r) updF(l , r , i << 1 , val) , updF(l , r , (i << 1) | 1 , val);
}
ll getF(int i){
    ll res = seg[0][i];
    while(i > 1) i >>= 1 , res = min(res , seg[0][i]);
    return res;
}
void updPt(int i , ll val){
    while(i >= 1) seg[1][i] = min(seg[1][i] , val) , bck[bckcnt][0] = 1 , bck[bckcnt++][1] = i , i >>= 1;
}
ll getPt(int l , int r , int i){
    if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[1][i];
    if(seginf[i][1] >= l and seginf[i][0] <= r) return min(getPt(l , r , i << 1) , getPt(l , r , (i << 1) | 1));
    return INF;
}
void ersSeg(){
    for(int i = 0 ; i < bckcnt ; i++) seg[bck[i][0]][bck[i][1]] = INF;
    bckcnt = 0;
}
void dfs1(int v = 0){
    if(v == 0) p[0] = -1;
    cmp[v] = 1;
    for(auto d : tr[v]){
        int u = d[0] , c = d[1];
        if(u == p[v]) continue;
        p[u] = v , h[u] = h[v] + (1ll * c);
        dfs1(u);
        cmp[v] += cmp[u];
    }
}
int timer = 0;
void dfs2(int v = 0){
    id[v] = timer++;
    int u = -1;
    for(auto el : tr[v]){
        if(el[0] == p[v]) continue;
        if(u == -1 or cmp[u] < cmp[el[0]]) u = el[0];
    }
    if(u == -1) return;
    r[u] = r[v] , dfs2(u);
    for(auto el : tr[v]){
        if(el[0] == p[v] or el[0] == u) continue;
        r[el[0]] = el[0] , dfs2(el[0]);
    }
}
void Init(int N , int *A , int *B , int *D){
    n = N;
    for(int i = 0 ; i < n - 1 ; i++) tr[A[i]].pb({B[i] , D[i]}) , tr[B[i]].pb({A[i] , D[i]});
    dfs1() , dfs2() , buildSeg();
}
long long Query(int S , int *X , int T , int *Y){
    for(int i = 0 ; i < T ; i++){
        int v = Y[i] , cur = v;
        while(cur != -1){
            updF(id[r[cur]] , id[cur] , 1 , h[v]);
            updPt(is[id[cur]] , h[v] - h[cur] - h[cur]);
            cur = p[r[cur]];
        }
    }
    ll res = INF;
    for(int i = 0 ; i < S ; i++){
        int v = X[i] , cur = v;
        while(cur != -1){
            res = min(res , h[v] + getF(is[id[cur]]) - h[cur] - h[cur]);
            res = min(res , h[v] + getPt(id[r[cur]] , id[cur] , 1));
            cur = p[r[cur]];
        }
    }
    ersSeg();
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43608 KB Output is correct
2 Correct 980 ms 59828 KB Output is correct
3 Correct 855 ms 57712 KB Output is correct
4 Correct 974 ms 59840 KB Output is correct
5 Correct 436 ms 60240 KB Output is correct
6 Correct 553 ms 59732 KB Output is correct
7 Correct 817 ms 57512 KB Output is correct
8 Correct 777 ms 59812 KB Output is correct
9 Correct 442 ms 60132 KB Output is correct
10 Correct 557 ms 59996 KB Output is correct
11 Correct 828 ms 57704 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43612 KB Output is correct
2 Correct 3423 ms 113344 KB Output is correct
3 Correct 2656 ms 116364 KB Output is correct
4 Correct 1651 ms 113920 KB Output is correct
5 Correct 1574 ms 144640 KB Output is correct
6 Correct 2834 ms 117124 KB Output is correct
7 Correct 1377 ms 70992 KB Output is correct
8 Correct 903 ms 70568 KB Output is correct
9 Correct 821 ms 74144 KB Output is correct
10 Correct 1478 ms 71392 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43608 KB Output is correct
2 Correct 980 ms 59828 KB Output is correct
3 Correct 855 ms 57712 KB Output is correct
4 Correct 974 ms 59840 KB Output is correct
5 Correct 436 ms 60240 KB Output is correct
6 Correct 553 ms 59732 KB Output is correct
7 Correct 817 ms 57512 KB Output is correct
8 Correct 777 ms 59812 KB Output is correct
9 Correct 442 ms 60132 KB Output is correct
10 Correct 557 ms 59996 KB Output is correct
11 Correct 828 ms 57704 KB Output is correct
12 Correct 10 ms 43612 KB Output is correct
13 Correct 3423 ms 113344 KB Output is correct
14 Correct 2656 ms 116364 KB Output is correct
15 Correct 1651 ms 113920 KB Output is correct
16 Correct 1574 ms 144640 KB Output is correct
17 Correct 2834 ms 117124 KB Output is correct
18 Correct 1377 ms 70992 KB Output is correct
19 Correct 903 ms 70568 KB Output is correct
20 Correct 821 ms 74144 KB Output is correct
21 Correct 1478 ms 71392 KB Output is correct
22 Correct 6385 ms 156956 KB Output is correct
23 Correct 5913 ms 119936 KB Output is correct
24 Correct 4929 ms 144456 KB Output is correct
25 Correct 4812 ms 147028 KB Output is correct
26 Correct 4839 ms 122460 KB Output is correct
27 Correct 2684 ms 156184 KB Output is correct
28 Correct 2888 ms 137372 KB Output is correct
29 Correct 4811 ms 121992 KB Output is correct
30 Correct 4847 ms 119312 KB Output is correct
31 Correct 4632 ms 120100 KB Output is correct
32 Correct 901 ms 89564 KB Output is correct
33 Correct 1032 ms 87344 KB Output is correct
34 Correct 2037 ms 71884 KB Output is correct
35 Correct 2049 ms 71888 KB Output is correct
36 Correct 1431 ms 72528 KB Output is correct
37 Correct 1426 ms 72508 KB Output is correct