oj.uz

답안 #930883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930883 2024-02-20T15:03:14 Z parlimoos 공장들 (JOI14_factories) C++14
0 / 100
 28 ms 43608 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();
}
ll 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]);
            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) - h[cur]);
            cur = p[r[cur]];
        }
    }
    ersSeg();
    return res;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 43608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 43352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 43608 KB Output isn't correct
2 Halted 0 ms 0 KB -