oj.uz

Submission #414703

# Submission time Handle Problem Language Result Execution time Memory
414703 2021-05-31T04:46:16 Z 조영욱(#7631) Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 883 ms 196928 KB 
#include <bits/stdc++.h>
using namespace std;

int arr[5001];
int cost[5001];
vector<int> son[5001];
long long dp[5001][5001];
vector<int> press;

long long ans(int v,int c) {
    if (dp[v][c]!=-1) {
        return dp[v][c];
    }
    long long ret=0;
    if (c!=arr[v]) {
        ret+=cost[v];
    }
    for(int i=0;i<son[v].size();i++) {
        long long val=ans(son[v][i],c);
        if (arr[son[v][i]]>=c) {
            val=min(val,ans(son[v][i],arr[son[v][i]]));
        }
        ret+=val;
    }
    return dp[v][c]=ret;
}

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int p;
        scanf("%d %d %d",&p,&arr[i],&cost[i]);
        press.push_back(arr[i]);
        if (i!=1) {
            son[p].push_back(i);
        }
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=1;i<=n;i++) {
        arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld",min(ans(1,0),ans(1,arr[1])));
}

Compilation message

worst_reporter2.cpp: In function 'long long int ans(int, int)':
worst_reporter2.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
worst_reporter2.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d %d %d",&p,&arr[i],&cost[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 196112 KB Output is correct
2 Correct 87 ms 196064 KB Output is correct
3 Correct 88 ms 196176 KB Output is correct
4 Correct 87 ms 196124 KB Output is correct
5 Correct 95 ms 196436 KB Output is correct
6 Correct 94 ms 196416 KB Output is correct
7 Correct 95 ms 196420 KB Output is correct
8 Correct 98 ms 196500 KB Output is correct
9 Correct 95 ms 196316 KB Output is correct
10 Correct 93 ms 196416 KB Output is correct
11 Correct 92 ms 196436 KB Output is correct
12 Correct 883 ms 196928 KB Output is correct
13 Correct 95 ms 196924 KB Output is correct
14 Correct 460 ms 196756 KB Output is correct
15 Correct 105 ms 196616 KB Output is correct
16 Correct 95 ms 196364 KB Output is correct
17 Correct 92 ms 196384 KB Output is correct
18 Correct 90 ms 196424 KB Output is correct
19 Correct 555 ms 196628 KB Output is correct
20 Correct 105 ms 196548 KB Output is correct
21 Correct 91 ms 196532 KB Output is correct
22 Correct 90 ms 196396 KB Output is correct
23 Correct 91 ms 196292 KB Output is correct
24 Correct 704 ms 196644 KB Output is correct
25 Correct 106 ms 196548 KB Output is correct
26 Correct 432 ms 196880 KB Output is correct
27 Correct 285 ms 196684 KB Output is correct
28 Correct 447 ms 196696 KB Output is correct
29 Correct 589 ms 196808 KB Output is correct
30 Correct 413 ms 196756 KB Output is correct
31 Correct 424 ms 196628 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 196352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 196112 KB Output is correct
2 Correct 87 ms 196064 KB Output is correct
3 Correct 88 ms 196176 KB Output is correct
4 Correct 87 ms 196124 KB Output is correct
5 Correct 95 ms 196436 KB Output is correct
6 Correct 94 ms 196416 KB Output is correct
7 Correct 95 ms 196420 KB Output is correct
8 Correct 98 ms 196500 KB Output is correct
9 Correct 95 ms 196316 KB Output is correct
10 Correct 93 ms 196416 KB Output is correct
11 Correct 92 ms 196436 KB Output is correct
12 Correct 883 ms 196928 KB Output is correct
13 Correct 95 ms 196924 KB Output is correct
14 Correct 460 ms 196756 KB Output is correct
15 Correct 105 ms 196616 KB Output is correct
16 Correct 95 ms 196364 KB Output is correct
17 Correct 92 ms 196384 KB Output is correct
18 Correct 90 ms 196424 KB Output is correct
19 Correct 555 ms 196628 KB Output is correct
20 Correct 105 ms 196548 KB Output is correct
21 Correct 91 ms 196532 KB Output is correct
22 Correct 90 ms 196396 KB Output is correct
23 Correct 91 ms 196292 KB Output is correct
24 Correct 704 ms 196644 KB Output is correct
25 Correct 106 ms 196548 KB Output is correct
26 Correct 432 ms 196880 KB Output is correct
27 Correct 285 ms 196684 KB Output is correct
28 Correct 447 ms 196696 KB Output is correct
29 Correct 589 ms 196808 KB Output is correct
30 Correct 413 ms 196756 KB Output is correct
31 Correct 424 ms 196628 KB Output is correct
32 Incorrect 96 ms 196352 KB Output isn't correct
33 Halted 0 ms 0 KB -