Submission #1227533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227533		KindaGoodGames	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	319 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<vector<int>> dp;
vector<vector<int>> adj;
int n;
void DFS(int v){
    for(auto u : adj[v]){
        DFS(u);
    }

    vector<int> minis(adj[v].size(), INF);
    for(int k = n-1; k >= 0; k--){
        int add = 0;
        if(k != arr[v]){
            add = cost[v];
        }

        int c = 0;
        for(int i = 0; i < adj[v].size(); i++){
            minis[i] = min(minis[i], dp[adj[v][i]][k]);
            c += minis[i];
        }

        dp[v][k] = add + c;
    }
}

int32_t main(){
    cin >> n;
    cost = arr = par = vector<int>(n);
    dp.resize(n, vector<int>(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);
    int mi = INF;
    for(int i = 0; i < n; i++){
        mi = min(mi, dp[0][i]);
    }
    cout << mi << endl;
}

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