oj.uz

Submission #531428

# Submission time Handle Problem Language Result Execution time Memory
531428 2022-02-28T16:52:59 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, a[N], lab[N], b[N], tong, d[N], t, 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(auto x: mp[v])mp[u][x.fi] += x.se;
    }
    if(b[u])
    {
        mp[u][b[u]] += a[u];
        map<int, ll>:: iterator it = mp[u].upper_bound(b[u]), nxt;
        for(; it != mp[u].end(); it = nxt)
        {
            if(a[u] < it->se)
            {
                it->se -= a[u];

                break;
            }
            else
            {
                a[u] -= it->se;
                nxt = next(it);
                mp[u].erase(it);
            }
        }
    }
    /*
    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(auto 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:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9704 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9716 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 363 ms 129420 KB Output is correct
2 Runtime error 1898 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 11340 KB Output is correct
3 Correct 39 ms 22268 KB Output is correct
4 Correct 99 ms 62224 KB Output is correct
5 Execution timed out 2098 ms 1036552 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22584 KB Output is correct
2 Correct 94 ms 19268 KB Output is correct
3 Correct 81 ms 32120 KB Output is correct
4 Correct 54 ms 23360 KB Output is correct
5 Correct 66 ms 41396 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9704 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9716 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 143 ms 41288 KB Output is correct
11 Correct 133 ms 33664 KB Output is correct
12 Correct 281 ms 139332 KB Output is correct
13 Correct 245 ms 124568 KB Output is correct
14 Correct 264 ms 146588 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11260 KB Output is correct
2 Correct 36 ms 14004 KB Output is correct
3 Correct 62 ms 14168 KB Output is correct
4 Correct 38 ms 14692 KB Output is correct
5 Correct 96 ms 42180 KB Output is correct
6 Correct 684 ms 281588 KB Output is correct
7 Correct 689 ms 305732 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9704 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9716 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 10060 KB Output is correct
11 Correct 9 ms 11340 KB Output is correct
12 Correct 39 ms 22268 KB Output is correct
13 Correct 99 ms 62224 KB Output is correct
14 Execution timed out 2098 ms 1036552 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 9704 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9716 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 363 ms 129420 KB Output is correct
11 Runtime error 1898 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -