oj.uz

Submission #475418

# Submission time Handle Problem Language Result Execution time Memory
475418 2021-09-22T10:13:52 Z nafis_shifat Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 5 ms 716 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e3+5;
const int inf=1e9;


ll c[mxn];
int h[mxn];
vector<int> adj[mxn];

ll dp[mxn][mxn];
ll suf[mxn][mxn];

int n;

void dfs(int u) {
    for(int v : adj[u]) dfs(v);

    for(int i = 1; i <= n; i++) {
        dp[u][i] = c[u];
        if(i == h[u]) dp[u][i] = 0;
        for(int v : adj[u]) {
            dp[u][i] += suf[v][i];
        }
    }

    suf[u][n] = dp[u][n];



    for(int i = n - 1; i >= 1; i--) {
        suf[u][i] = min(suf[u][i + 1],dp[u][i]);
    }
}

int main() {
    cin >> n;

    vector<int> v;

    for(int i = 1; i <= n; i++) {
        int bap;
        scanf("%d %d %lld",&bap,&h[i],&c[i]);
        if(bap != i) adj[bap].push_back(i);
        v.push_back(h[i]);
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()), v.end());

    for(int i = 1; i <= n; i++) {
        h[i] = lower_bound(v.begin(),v.end(),h[i]) - v.begin() + 1;
    }

    dfs(1);

    cout<<suf[1][1]<<endl;







}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d %lld",&bap,&h[i],&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Runtime error 5 ms 716 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Runtime error 5 ms 716 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Runtime error 5 ms 716 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -