Submission #398750

#	Time	Username	Problem	Language	Result	Execution time	Memory
398750		4fecta	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	668 ms	524288 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 5005;

int n, a[MN], h[MN], c[MN], dp[MN][MN], suf[MN][MN];
vector<int> hs, adj[MN];
map<int, int> mp;

void dfs(int cur) {
    for (int i = 1; i <= hs.size(); i++) dp[cur][i] = i == h[cur] ? 0 : c[cur];
    for (int nxt : adj[cur]) {
        dfs(nxt);
        for (int i = 1; i <= hs.size(); i++) dp[cur][i] += suf[nxt][i];
    }
    for (int i = hs.size(); i > 0; i--) suf[cur][i] = min(dp[cur][i], suf[cur][i + 1]);
}

int32_t main() {
    boost();

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> h[i] >> c[i];
        if (i > 1) adj[a[i]].push_back(i);
        hs.push_back(h[i]);
    }
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());
    for (int i = 0; i < hs.size(); i++) mp[hs[i]] = i + 1;
    for (int i = 1; i <= n; i++) h[i] = mp[h[i]];
    memset(dp, 0x3f, sizeof(dp));
    memset(suf, 0x3f, sizeof(suf));
    dfs(1);
    int ans = 1e18;
    for (int i = 1; i <= hs.size(); i++) ans = min(ans, dp[1][i]);
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs(long long int)':
worst_reporter2.cpp:18:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 1; i <= hs.size(); i++) dp[cur][i] = i == h[cur] ? 0 : c[cur];
      |                     ~~^~~~~~~~~~~~
worst_reporter2.cpp:21:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i = 1; i <= hs.size(); i++) dp[cur][i] += suf[nxt][i];
      |                         ~~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'int32_t main()':
worst_reporter2.cpp:37:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < hs.size(); i++) mp[hs[i]] = i + 1;
      |                     ~~^~~~~~~~~~~
worst_reporter2.cpp:43:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i <= hs.size(); i++) ans = min(ans, dp[1][i]);
      |                     ~~^~~~~~~~~~~~

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