oj.uz

Submission #531422

# Submission time Handle Problem Language Result Execution time Memory
531422 2022-02-28T16:40:07 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];
ll ans, tong, d[N], t, a[N], c[N], dp[N], k;
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: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 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9652 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9652 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9736 KB Output is correct
8 Correct 5 ms 9748 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 129448 KB Output is correct
2 Runtime error 1916 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 5 ms 10060 KB Output is correct
2 Correct 8 ms 11340 KB Output is correct
3 Correct 35 ms 22280 KB Output is correct
4 Correct 105 ms 62124 KB Output is correct
5 Execution timed out 2074 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 86 ms 21572 KB Output is correct
2 Correct 76 ms 18452 KB Output is correct
3 Correct 65 ms 31188 KB Output is correct
4 Correct 46 ms 22472 KB Output is correct
5 Correct 61 ms 40516 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 5 ms 9676 KB Output is correct
3 Correct 6 ms 9652 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9652 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9736 KB Output is correct
8 Correct 5 ms 9748 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 129 ms 40480 KB Output is correct
11 Correct 109 ms 32780 KB Output is correct
12 Correct 269 ms 138496 KB Output is correct
13 Correct 213 ms 123912 KB Output is correct
14 Correct 249 ms 145820 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11264 KB Output is correct
2 Correct 29 ms 13896 KB Output is correct
3 Correct 31 ms 13928 KB Output is correct
4 Correct 35 ms 14484 KB Output is correct
5 Correct 81 ms 42560 KB Output is correct
6 Correct 708 ms 281988 KB Output is correct
7 Correct 668 ms 306272 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 5 ms 9676 KB Output is correct
3 Correct 6 ms 9652 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9652 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9736 KB Output is correct
8 Correct 5 ms 9748 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 10060 KB Output is correct
11 Correct 8 ms 11340 KB Output is correct
12 Correct 35 ms 22280 KB Output is correct
13 Correct 105 ms 62124 KB Output is correct
14 Execution timed out 2074 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 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9652 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9652 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9736 KB Output is correct
8 Correct 5 ms 9748 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 330 ms 129448 KB Output is correct
11 Runtime error 1916 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -