제출 #1227530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227530		KindaGoodGames	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	0 / 100	256 ms	589824 KiB

worst_reporter2

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define tiii tuple<int,int,int>

int INF = numeric_limits<int>::max()/2;

struct SegmentTree{
    vector<int> S;
    int len = 1;

    SegmentTree(int n){
        while(len < n) len <<= 1;
        S.resize(2*len, INF);
    }

    int query(int ql, int qr, int l = 0, int r = -1, int i = 1){
        if(r == -1) r = len;
        if(ql <= l && r <= qr) return S[i];
        if(r <= ql || qr <= l) return INF;

        int mid = (l+r)/2;

        return min(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
    }

    void upd(int i, int v){
        i += len;
        S[i] = v;

        for(i /= 2; i > 0; i/=2){
            S[i] = min(S[i*2], S[i*2+1]);
        }
    }
};


vector<int> arr;
vector<int> par;
vector<int> cost;
vector<SegmentTree> dp;
vector<vector<int>> adj;
int n;
void DFS(int v){
    for(auto u : adj[v]){
        DFS(u);
    }

    for(int k = 0; k < n; k++){
        int add = 0;
        if(k != arr[v]){
            add = cost[v];
        }

        int c = 0;
        for(auto u : adj[v]){
            c += dp[u].query(k, n+1);
        }

        dp[v].upd(k,add + c);
    }
}

int32_t main(){
    cin >> n;
    cost = arr = par = vector<int>(n);
    dp.resize(n, SegmentTree(n));
    adj.resize(n);
    for(int i = 0; i < n; i++){
        int a,h,c;
        cin >> a >> h >> c;

        a--;
        par[i] = a;
        arr[i] = h;
        cost[i] = c;
    }

    vector<int> sorted = arr;
    sort(sorted.begin(),sorted.end());
    map<int,int> toInd;
    for(int i = 0; i < n; i++){
        toInd[sorted[i]] = i;
    }
    for(int i = 0; i < n; i++){
        arr[i] = toInd[arr[i]];
    }

    for(int i = 1; i < n; i++){
        adj[par[i]].push_back(i);
    }

    DFS(0);
    cout << dp[0].query(0, n+1) << endl;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21