oj.uz

Submission #930893

# Submission time Handle Problem Language Result Execution time Memory
930893 2024-02-20T15:30:15 Z parlimoos Factories (JOI14_factories) C++14
100 / 100
 7222 ms 180968 KB 
#include "factories.h"

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.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];
vector<arr(2)> bck;

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.pb({0 , 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 /= 2 , 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.pb({1 , i}) , i /= 2;
}
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(auto &el : bck) seg[el[0]][el[1]] = INF;
    bck.cl();
}
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 31 ms 43612 KB Output is correct
2 Correct 1334 ms 58312 KB Output is correct
3 Correct 1088 ms 57608 KB Output is correct
4 Correct 1103 ms 57708 KB Output is correct
5 Correct 515 ms 57944 KB Output is correct
6 Correct 705 ms 57924 KB Output is correct
7 Correct 1062 ms 57608 KB Output is correct
8 Correct 987 ms 59456 KB Output is correct
9 Correct 512 ms 58048 KB Output is correct
10 Correct 734 ms 53876 KB Output is correct
11 Correct 1030 ms 57608 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43612 KB Output is correct
2 Correct 3953 ms 110216 KB Output is correct
3 Correct 2826 ms 113488 KB Output is correct
4 Correct 1810 ms 110672 KB Output is correct
5 Correct 1847 ms 141388 KB Output is correct
6 Correct 3099 ms 113996 KB Output is correct
7 Correct 1654 ms 75724 KB Output is correct
8 Correct 1097 ms 75520 KB Output is correct
9 Correct 1008 ms 79140 KB Output is correct
10 Correct 1750 ms 76316 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 43612 KB Output is correct
2 Correct 1334 ms 58312 KB Output is correct
3 Correct 1088 ms 57608 KB Output is correct
4 Correct 1103 ms 57708 KB Output is correct
5 Correct 515 ms 57944 KB Output is correct
6 Correct 705 ms 57924 KB Output is correct
7 Correct 1062 ms 57608 KB Output is correct
8 Correct 987 ms 59456 KB Output is correct
9 Correct 512 ms 58048 KB Output is correct
10 Correct 734 ms 53876 KB Output is correct
11 Correct 1030 ms 57608 KB Output is correct
12 Correct 11 ms 43612 KB Output is correct
13 Correct 3953 ms 110216 KB Output is correct
14 Correct 2826 ms 113488 KB Output is correct
15 Correct 1810 ms 110672 KB Output is correct
16 Correct 1847 ms 141388 KB Output is correct
17 Correct 3099 ms 113996 KB Output is correct
18 Correct 1654 ms 75724 KB Output is correct
19 Correct 1097 ms 75520 KB Output is correct
20 Correct 1008 ms 79140 KB Output is correct
21 Correct 1750 ms 76316 KB Output is correct
22 Correct 7222 ms 180968 KB Output is correct
23 Correct 6417 ms 117756 KB Output is correct
24 Correct 5783 ms 155192 KB Output is correct
25 Correct 5440 ms 156992 KB Output is correct
26 Correct 5457 ms 124368 KB Output is correct
27 Correct 3026 ms 162200 KB Output is correct
28 Correct 3121 ms 155176 KB Output is correct
29 Correct 5162 ms 123452 KB Output is correct
30 Correct 5190 ms 122688 KB Output is correct
31 Correct 5470 ms 123372 KB Output is correct
32 Correct 1111 ms 95924 KB Output is correct
33 Correct 1318 ms 91800 KB Output is correct
34 Correct 2723 ms 75240 KB Output is correct
35 Correct 2576 ms 75208 KB Output is correct
36 Correct 1749 ms 75248 KB Output is correct
37 Correct 1730 ms 75160 KB Output is correct