oj.uz

Submission #893865

# Submission time Handle Problem Language Result Execution time Memory
893865 2023-12-27T15:06:09 Z danikoynov Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 0 ms 348 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 5010;
const ll inf = 1e18;

int n, a[maxn], h[maxn];
ll c[maxn];
vector < int > adj[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> h[i] >> c[i];
        if (a[i] != i)
            adj[a[i]].push_back(i);
    }
}

unordered_map < int, int > tag;

void compress()
{
    vector < int > values;
    for (int i = 1; i <= n; i ++)
        values.push_back(h[i]);

    sort(values.begin(), values.end());

    for (int i = 0; i < n; i ++)
        tag[values[i]] = i + 1;

}

ll dp[maxn][maxn], temp[maxn];
int used[maxn];

void dfs(int v)
{


    used[v] = 1;
    for (int u : adj[v])
    {
        dfs(u);

        for (int j = n; j >= 1; j --)
        {
            dp[v][j] += dp[u][j];
        }
    }

        for (int j = tag[h[v]] + 1; j <= n; j ++)
    {
        if (j != tag[h[v]])
        dp[v][j] += c[v];
    }
    for (int j = n - 1; j > 0; j --)
    {
        dp[v][j] = min(dp[v][j], dp[v][j + 1]);
    }
    cout << "state " << v << " " << h[v] << endl;
    for (int j = 1; j <= n; j ++)
        cout << dp[v][j] << " ";
    cout << endl;
}
void calculate_states()
{
    ll ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;

        dfs(i);
        ll best = inf;
        for (int j = 1; j <= n; j ++)
        {
            best = min(best, dp[i][j]);
        }

        ans += best;
    }

    cout << ans << endl;
}
void solve()
{
    input();
    compress();
    calculate_states();
}

int main()
{
    solve();
    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 65.0

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

Subtask #3
0 / 21.0

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