oj.uz

Submission #894072

# Submission time Handle Problem Language Result Execution time Memory
894072 2023-12-28T00:03:00 Z danikoynov Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 457 ms 199432 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];
set < pair < int, ll > > spot[maxn];

void add_to_set(int v, pair < int, ll > cur)
{
    set < pair < int, ll > > :: iterator it = spot[v].lower_bound({v, -inf});
    if (it != spot[v].end() && it -> first == cur.first)
    {
        cur.second += it -> second;
        spot[v].erase(it);
    }
    spot[v].insert(cur);
}

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];
        }
        if (spot[u].size() > spot[v].size())
            swap(spot[v], spot[u]);

        for (pair < int, ll > cur : spot[u])
            add_to_set(v, cur);

    }

    set < pair < int, ll > > :: iterator it;
    ll sum = 0;
    while(spot[v].size() > 0)
    {

        it = spot[v].lower_bound({tag[h[v]], inf});
        if (it == spot[v].begin())
            break;
        it = prev(it);

        if (sum + it -> second > c[v])
        {
            pair < int, ll > nw = *it;
            nw.second -= (c[v] - sum);
            sum = c[v];
            spot[v].erase(it);
            add_to_set(v, nw);
            ///spot[v].insert(nw);
            break;
        }
        else
        {
            sum += it -> second;
            spot[v].erase(it);
        }

    }
    /**cout << "state " << v << " " << h[v] << endl;
    for (int j = 1; j <= n; j ++)
        cout << dp[v][j] << " ";
    cout << endl;
    for (pair < int, ll > cur : spot[v])
        cout << cur.first << " " << cur.second << endl;
    cout << "----------" << endl;*/
    add_to_set(v, {1, sum});
    add_to_set(v, {tag[h[v]] + 1, c[v]});
    ///add_to_set(v, {tag[h[v]] + 1, c[v] - sum});
    //spot[v].insert({1, sum});
    ///spot[v].insert({tag[h[v]] + 1, c[v] - sum});

    /**for (int j = 0; j <= n; j ++)
        temp[j] = 0;
    for (pair < int, ll > cur : spot[v])
        for (int d = cur.first; d <= n; d ++)
        temp[d] += cur.second;*/

    for (int j = 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]);
    }


    /**for (int j = 1; j <= n; j ++)
    {
        if (temp[j] != dp[v][j])
        {
            cout << "Fuck " << v << endl;
            for (int d = 1; d <= j + 10; d ++)
                cout << temp[d] << " " << dp[v][d] << endl;
                cout << "HERE " << tag[h[v]] << " " << j << " " << c[v] - sum << " " << sum << endl;
            exit(0);
        }
    }
    cout << "passed " << v << endl;*/

}
void calculate_states()
{
    ll ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;

        dfs(i);

        ll s = 0;
        for (pair < int, ll > cur : spot[i])
        {
            if (cur.first == 1)
                s += cur.second;
        }
        ans += s;
    }

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

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 386 ms 198624 KB Output is correct
6 Correct 379 ms 198840 KB Output is correct
7 Correct 357 ms 198248 KB Output is correct
8 Correct 370 ms 198824 KB Output is correct
9 Correct 394 ms 198556 KB Output is correct
10 Correct 360 ms 198476 KB Output is correct
11 Correct 318 ms 197436 KB Output is correct
12 Correct 361 ms 198476 KB Output is correct
13 Correct 457 ms 198060 KB Output is correct
14 Correct 360 ms 197924 KB Output is correct
15 Correct 364 ms 197716 KB Output is correct
16 Correct 363 ms 199432 KB Output is correct
17 Correct 374 ms 199232 KB Output is correct
18 Correct 299 ms 197332 KB Output is correct
19 Correct 356 ms 198224 KB Output is correct
20 Correct 391 ms 198108 KB Output is correct
21 Correct 348 ms 198064 KB Output is correct
22 Correct 358 ms 198232 KB Output is correct
23 Correct 368 ms 198112 KB Output is correct
24 Correct 359 ms 198260 KB Output is correct
25 Correct 370 ms 198228 KB Output is correct
26 Incorrect 360 ms 197968 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 386 ms 198624 KB Output is correct
6 Correct 379 ms 198840 KB Output is correct
7 Correct 357 ms 198248 KB Output is correct
8 Correct 370 ms 198824 KB Output is correct
9 Correct 394 ms 198556 KB Output is correct
10 Correct 360 ms 198476 KB Output is correct
11 Correct 318 ms 197436 KB Output is correct
12 Correct 361 ms 198476 KB Output is correct
13 Correct 457 ms 198060 KB Output is correct
14 Correct 360 ms 197924 KB Output is correct
15 Correct 364 ms 197716 KB Output is correct
16 Correct 363 ms 199432 KB Output is correct
17 Correct 374 ms 199232 KB Output is correct
18 Correct 299 ms 197332 KB Output is correct
19 Correct 356 ms 198224 KB Output is correct
20 Correct 391 ms 198108 KB Output is correct
21 Correct 348 ms 198064 KB Output is correct
22 Correct 358 ms 198232 KB Output is correct
23 Correct 368 ms 198112 KB Output is correct
24 Correct 359 ms 198260 KB Output is correct
25 Correct 370 ms 198228 KB Output is correct
26 Incorrect 360 ms 197968 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 386 ms 198624 KB Output is correct
6 Correct 379 ms 198840 KB Output is correct
7 Correct 357 ms 198248 KB Output is correct
8 Correct 370 ms 198824 KB Output is correct
9 Correct 394 ms 198556 KB Output is correct
10 Correct 360 ms 198476 KB Output is correct
11 Correct 318 ms 197436 KB Output is correct
12 Correct 361 ms 198476 KB Output is correct
13 Correct 457 ms 198060 KB Output is correct
14 Correct 360 ms 197924 KB Output is correct
15 Correct 364 ms 197716 KB Output is correct
16 Correct 363 ms 199432 KB Output is correct
17 Correct 374 ms 199232 KB Output is correct
18 Correct 299 ms 197332 KB Output is correct
19 Correct 356 ms 198224 KB Output is correct
20 Correct 391 ms 198108 KB Output is correct
21 Correct 348 ms 198064 KB Output is correct
22 Correct 358 ms 198232 KB Output is correct
23 Correct 368 ms 198112 KB Output is correct
24 Correct 359 ms 198260 KB Output is correct
25 Correct 370 ms 198228 KB Output is correct
26 Incorrect 360 ms 197968 KB Output isn't correct
27 Halted 0 ms 0 KB -