oj.uz

Submission #531424

# Submission time Handle Problem Language Result Execution time Memory
531424 2022-02-28T16:43:06 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], tong, d[N], t, c[N], dp[N], k;
ll a[N], 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])
    {
        ll 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:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 129368 KB Output is correct
2 Runtime error 1873 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 9992 KB Output is correct
2 Correct 8 ms 11340 KB Output is correct
3 Correct 33 ms 22336 KB Output is correct
4 Correct 97 ms 62200 KB Output is correct
5 Execution timed out 2116 ms 1048580 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 21600 KB Output is correct
2 Correct 77 ms 18400 KB Output is correct
3 Correct 63 ms 31168 KB Output is correct
4 Correct 45 ms 22444 KB Output is correct
5 Correct 58 ms 40568 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9612 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9732 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 127 ms 40340 KB Output is correct
11 Correct 114 ms 32840 KB Output is correct
12 Correct 263 ms 138444 KB Output is correct
13 Correct 219 ms 124000 KB Output is correct
14 Correct 244 ms 145888 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11212 KB Output is correct
2 Correct 31 ms 13820 KB Output is correct
3 Correct 31 ms 13900 KB Output is correct
4 Correct 34 ms 14472 KB Output is correct
5 Correct 76 ms 42376 KB Output is correct
6 Correct 695 ms 281388 KB Output is correct
7 Correct 634 ms 305576 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9612 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9732 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9992 KB Output is correct
11 Correct 8 ms 11340 KB Output is correct
12 Correct 33 ms 22336 KB Output is correct
13 Correct 97 ms 62200 KB Output is correct
14 Execution timed out 2116 ms 1048580 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9612 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9732 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 334 ms 129368 KB Output is correct
11 Runtime error 1873 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -