oj.uz

Submission #531427

# Submission time Handle Problem Language Result Execution time Memory
531427 2022-02-28T16:52:19 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(pii 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(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: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 5 ms 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9716 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 129240 KB Output is correct
2 Runtime error 1902 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 11412 KB Output is correct
3 Correct 34 ms 22268 KB Output is correct
4 Correct 96 ms 62716 KB Output is correct
5 Execution timed out 2075 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 77 ms 21700 KB Output is correct
2 Correct 72 ms 18792 KB Output is correct
3 Correct 76 ms 31548 KB Output is correct
4 Correct 49 ms 22928 KB Output is correct
5 Correct 60 ms 40940 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9716 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 123 ms 40752 KB Output is correct
11 Correct 108 ms 33188 KB Output is correct
12 Correct 253 ms 138816 KB Output is correct
13 Correct 211 ms 124348 KB Output is correct
14 Correct 240 ms 146184 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11212 KB Output is correct
2 Correct 30 ms 14020 KB Output is correct
3 Correct 32 ms 14076 KB Output is correct
4 Correct 32 ms 14708 KB Output is correct
5 Correct 80 ms 42308 KB Output is correct
6 Correct 666 ms 281680 KB Output is correct
7 Correct 699 ms 305892 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9716 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 6 ms 10060 KB Output is correct
11 Correct 9 ms 11412 KB Output is correct
12 Correct 34 ms 22268 KB Output is correct
13 Correct 96 ms 62716 KB Output is correct
14 Execution timed out 2075 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 9680 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9716 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 326 ms 129240 KB Output is correct
11 Runtime error 1902 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -