oj.uz

Submission #531423

# Submission time Handle Problem Language Result Execution time Memory
531423 2022-02-28T16:40:53 Z Killer2501 Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 1048580 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, ll>
#define fi first
#define se second
using namespace std;
const int N = 1e5+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const ll inf = 1e16;
int n, m, lab[N], b[N];
int tong, d[N], t, a[N], c[N], dp[N], k;
ll ans;
vector<int> adj[N], radj[N];
vector<pll> vi;
string s;
map<int, ll> mp[N];
void dfs(int u)
{
    for(int v: adj[u])
    {
        dfs(v);
        if(mp[v].empty())continue;
        if(mp[u].size() > mp[v].size())swap(mp[u], mp[v]);
        for(pii x: mp[v])mp[u][x.fi] += x.se;
    }
    if(b[u])
    {
        t = a[u];
        while(true)
        {
            auto it = mp[u].upper_bound(b[u]);
            if(it == mp[u].end())break;
            if(t >= (*it).se)
            {
                t -= (*it).se;
                mp[u].erase(it);
            }
            else
            {
                mp[u][(*it).fi] -= t;
                break;
            }

        }
        mp[u][b[u]] += a[u];
    }
    /*
    cout << u << " "<<b[u]<<" "<<a[u]<< '\n';
    for(auto x: mp[u])cout << x.fi <<" "<<x.se<<'\n';
    */
}
void sol()
{
    cin >> n >> m >> k;
    for(int i = 2; i <= n; i ++)
    {
        cin >> t;
        adj[t].pb(i);
    }
    for(int i = 1; i <= m; i ++)
    {
        cin >> t;
        cin >> b[t] >> a[t];
    }
    dfs(1);
    if(!mp[1].empty())for(pii x: mp[1])ans += x.se;
    cout << ans;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
1234
21
*/

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9728 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 128916 KB Output is correct
2 Runtime error 1988 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10060 KB Output is correct
2 Correct 9 ms 11396 KB Output is correct
3 Correct 42 ms 22336 KB Output is correct
4 Correct 101 ms 61784 KB Output is correct
5 Execution timed out 2128 ms 1031016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 21188 KB Output is correct
2 Correct 75 ms 18052 KB Output is correct
3 Correct 71 ms 30880 KB Output is correct
4 Correct 47 ms 22116 KB Output is correct
5 Correct 66 ms 40180 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9728 KB Output is correct
10 Correct 133 ms 39940 KB Output is correct
11 Correct 119 ms 32484 KB Output is correct
12 Correct 276 ms 138096 KB Output is correct
13 Correct 222 ms 123564 KB Output is correct
14 Correct 261 ms 145412 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11076 KB Output is correct
2 Correct 38 ms 13468 KB Output is correct
3 Correct 46 ms 13612 KB Output is correct
4 Correct 36 ms 14148 KB Output is correct
5 Correct 85 ms 41952 KB Output is correct
6 Correct 690 ms 281108 KB Output is correct
7 Correct 669 ms 305212 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9728 KB Output is correct
10 Correct 6 ms 10060 KB Output is correct
11 Correct 9 ms 11396 KB Output is correct
12 Correct 42 ms 22336 KB Output is correct
13 Correct 101 ms 61784 KB Output is correct
14 Execution timed out 2128 ms 1031016 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9728 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9728 KB Output is correct
10 Correct 359 ms 128916 KB Output is correct
11 Runtime error 1988 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -