oj.uz

Submission #893859

# Submission time Handle Problem Language Result Execution time Memory
893859 2023-12-27T14:58:32 Z danikoynov Worst Reporter 4 (JOI21_worst_reporter4) C++14
14 / 100
 398 ms 398656 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)
{
    for (int j = 1; j <= n; j ++)
    {
        dp[v][j] = c[v];
        if (j == tag[h[v]])
            dp[v][j] = 0;
    }

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

        ll best = inf;
        for (int j = n; j >= 1; j --)
        {
            best = min(best, dp[u][j]);
            dp[v][j] += best;
        }
    }

    /**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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 324 ms 196948 KB Output is correct
6 Correct 316 ms 196868 KB Output is correct
7 Correct 295 ms 197100 KB Output is correct
8 Correct 297 ms 196944 KB Output is correct
9 Correct 331 ms 196948 KB Output is correct
10 Correct 294 ms 196804 KB Output is correct
11 Correct 258 ms 196948 KB Output is correct
12 Correct 300 ms 197528 KB Output is correct
13 Correct 398 ms 197364 KB Output is correct
14 Correct 302 ms 197332 KB Output is correct
15 Correct 305 ms 196976 KB Output is correct
16 Correct 302 ms 197000 KB Output is correct
17 Correct 316 ms 196852 KB Output is correct
18 Correct 240 ms 196944 KB Output is correct
19 Correct 300 ms 197260 KB Output is correct
20 Correct 330 ms 197032 KB Output is correct
21 Correct 297 ms 196932 KB Output is correct
22 Correct 299 ms 196912 KB Output is correct
23 Correct 310 ms 196812 KB Output is correct
24 Correct 303 ms 197148 KB Output is correct
25 Correct 322 ms 197060 KB Output is correct
26 Correct 302 ms 197456 KB Output is correct
27 Correct 302 ms 197112 KB Output is correct
28 Correct 298 ms 197204 KB Output is correct
29 Correct 297 ms 197416 KB Output is correct
30 Correct 297 ms 197204 KB Output is correct
31 Correct 298 ms 197488 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 324 ms 196948 KB Output is correct
6 Correct 316 ms 196868 KB Output is correct
7 Correct 295 ms 197100 KB Output is correct
8 Correct 297 ms 196944 KB Output is correct
9 Correct 331 ms 196948 KB Output is correct
10 Correct 294 ms 196804 KB Output is correct
11 Correct 258 ms 196948 KB Output is correct
12 Correct 300 ms 197528 KB Output is correct
13 Correct 398 ms 197364 KB Output is correct
14 Correct 302 ms 197332 KB Output is correct
15 Correct 305 ms 196976 KB Output is correct
16 Correct 302 ms 197000 KB Output is correct
17 Correct 316 ms 196852 KB Output is correct
18 Correct 240 ms 196944 KB Output is correct
19 Correct 300 ms 197260 KB Output is correct
20 Correct 330 ms 197032 KB Output is correct
21 Correct 297 ms 196932 KB Output is correct
22 Correct 299 ms 196912 KB Output is correct
23 Correct 310 ms 196812 KB Output is correct
24 Correct 303 ms 197148 KB Output is correct
25 Correct 322 ms 197060 KB Output is correct
26 Correct 302 ms 197456 KB Output is correct
27 Correct 302 ms 197112 KB Output is correct
28 Correct 298 ms 197204 KB Output is correct
29 Correct 297 ms 197416 KB Output is correct
30 Correct 297 ms 197204 KB Output is correct
31 Correct 298 ms 197488 KB Output is correct
32 Correct 300 ms 196948 KB Output is correct
33 Runtime error 308 ms 398656 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 324 ms 196948 KB Output is correct
6 Correct 316 ms 196868 KB Output is correct
7 Correct 295 ms 197100 KB Output is correct
8 Correct 297 ms 196944 KB Output is correct
9 Correct 331 ms 196948 KB Output is correct
10 Correct 294 ms 196804 KB Output is correct
11 Correct 258 ms 196948 KB Output is correct
12 Correct 300 ms 197528 KB Output is correct
13 Correct 398 ms 197364 KB Output is correct
14 Correct 302 ms 197332 KB Output is correct
15 Correct 305 ms 196976 KB Output is correct
16 Correct 302 ms 197000 KB Output is correct
17 Correct 316 ms 196852 KB Output is correct
18 Correct 240 ms 196944 KB Output is correct
19 Correct 300 ms 197260 KB Output is correct
20 Correct 330 ms 197032 KB Output is correct
21 Correct 297 ms 196932 KB Output is correct
22 Correct 299 ms 196912 KB Output is correct
23 Correct 310 ms 196812 KB Output is correct
24 Correct 303 ms 197148 KB Output is correct
25 Correct 322 ms 197060 KB Output is correct
26 Correct 302 ms 197456 KB Output is correct
27 Correct 302 ms 197112 KB Output is correct
28 Correct 298 ms 197204 KB Output is correct
29 Correct 297 ms 197416 KB Output is correct
30 Correct 297 ms 197204 KB Output is correct
31 Correct 298 ms 197488 KB Output is correct
32 Correct 300 ms 196948 KB Output is correct
33 Runtime error 308 ms 398656 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -