oj.uz

Submission #894073

# Submission time Handle Problem Language Result Execution time Memory
894073 2023-12-28T00:12:35 Z danikoynov Worst Reporter 4 (JOI21_worst_reporter4) C++14
14 / 100
 13 ms 7260 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({cur.first, -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);

        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].end())

        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});



}
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()
{
    speed();
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Subtask #1
14.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 6 ms 4188 KB Output is correct
6 Correct 5 ms 3420 KB Output is correct
7 Correct 4 ms 3420 KB Output is correct
8 Correct 6 ms 4188 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 3 ms 3172 KB Output is correct
12 Correct 5 ms 3672 KB Output is correct
13 Correct 4 ms 3420 KB Output is correct
14 Correct 6 ms 3416 KB Output is correct
15 Correct 4 ms 3416 KB Output is correct
16 Correct 7 ms 4444 KB Output is correct
17 Correct 5 ms 3856 KB Output is correct
18 Correct 3 ms 3180 KB Output is correct
19 Correct 5 ms 3676 KB Output is correct
20 Correct 4 ms 3420 KB Output is correct
21 Correct 5 ms 3420 KB Output is correct
22 Correct 5 ms 3932 KB Output is correct
23 Correct 3 ms 3416 KB Output is correct
24 Correct 6 ms 3872 KB Output is correct
25 Correct 4 ms 3528 KB Output is correct
26 Correct 3 ms 3676 KB Output is correct
27 Correct 6 ms 3932 KB Output is correct
28 Correct 5 ms 3932 KB Output is correct
29 Correct 5 ms 3932 KB Output is correct
30 Correct 6 ms 4000 KB Output is correct
31 Correct 5 ms 3932 KB Output is correct

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 6 ms 4188 KB Output is correct
6 Correct 5 ms 3420 KB Output is correct
7 Correct 4 ms 3420 KB Output is correct
8 Correct 6 ms 4188 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 3 ms 3172 KB Output is correct
12 Correct 5 ms 3672 KB Output is correct
13 Correct 4 ms 3420 KB Output is correct
14 Correct 6 ms 3416 KB Output is correct
15 Correct 4 ms 3416 KB Output is correct
16 Correct 7 ms 4444 KB Output is correct
17 Correct 5 ms 3856 KB Output is correct
18 Correct 3 ms 3180 KB Output is correct
19 Correct 5 ms 3676 KB Output is correct
20 Correct 4 ms 3420 KB Output is correct
21 Correct 5 ms 3420 KB Output is correct
22 Correct 5 ms 3932 KB Output is correct
23 Correct 3 ms 3416 KB Output is correct
24 Correct 6 ms 3872 KB Output is correct
25 Correct 4 ms 3528 KB Output is correct
26 Correct 3 ms 3676 KB Output is correct
27 Correct 6 ms 3932 KB Output is correct
28 Correct 5 ms 3932 KB Output is correct
29 Correct 5 ms 3932 KB Output is correct
30 Correct 6 ms 4000 KB Output is correct
31 Correct 5 ms 3932 KB Output is correct
32 Correct 8 ms 4188 KB Output is correct
33 Runtime error 13 ms 7260 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 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 6 ms 4188 KB Output is correct
6 Correct 5 ms 3420 KB Output is correct
7 Correct 4 ms 3420 KB Output is correct
8 Correct 6 ms 4188 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 3 ms 3172 KB Output is correct
12 Correct 5 ms 3672 KB Output is correct
13 Correct 4 ms 3420 KB Output is correct
14 Correct 6 ms 3416 KB Output is correct
15 Correct 4 ms 3416 KB Output is correct
16 Correct 7 ms 4444 KB Output is correct
17 Correct 5 ms 3856 KB Output is correct
18 Correct 3 ms 3180 KB Output is correct
19 Correct 5 ms 3676 KB Output is correct
20 Correct 4 ms 3420 KB Output is correct
21 Correct 5 ms 3420 KB Output is correct
22 Correct 5 ms 3932 KB Output is correct
23 Correct 3 ms 3416 KB Output is correct
24 Correct 6 ms 3872 KB Output is correct
25 Correct 4 ms 3528 KB Output is correct
26 Correct 3 ms 3676 KB Output is correct
27 Correct 6 ms 3932 KB Output is correct
28 Correct 5 ms 3932 KB Output is correct
29 Correct 5 ms 3932 KB Output is correct
30 Correct 6 ms 4000 KB Output is correct
31 Correct 5 ms 3932 KB Output is correct
32 Correct 8 ms 4188 KB Output is correct
33 Runtime error 13 ms 7260 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -