oj.uz

Submission #531432

# Submission time Handle Problem Language Result Execution time Memory
531432 2022-02-28T16:56:38 Z Killer2501 Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 1046520 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;
        ll v = a[u];
        for(; it != mp[u].end(); it = nxt)
        {
            if(v < it->se)
            {
                it->se -= v;
                break;
            }
            else
            {
                v -= 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 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 9676 KB Output is correct
8 Correct 6 ms 9716 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 348 ms 130040 KB Output is correct
2 Execution timed out 2131 ms 1046520 KB Time limit exceeded
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 36 ms 22284 KB Output is correct
4 Correct 101 ms 63068 KB Output is correct
5 Execution timed out 2079 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 88 ms 21332 KB Output is correct
2 Correct 79 ms 18380 KB Output is correct
3 Correct 73 ms 31152 KB Output is correct
4 Correct 61 ms 22468 KB Output is correct
5 Correct 63 ms 40548 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 5 ms 9676 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 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 9676 KB Output is correct
8 Correct 6 ms 9716 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 146 ms 40340 KB Output is correct
11 Correct 108 ms 32708 KB Output is correct
12 Correct 284 ms 138412 KB Output is correct
13 Correct 219 ms 123804 KB Output is correct
14 Correct 249 ms 145716 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11216 KB Output is correct
2 Correct 48 ms 13528 KB Output is correct
3 Correct 34 ms 13724 KB Output is correct
4 Correct 47 ms 14192 KB Output is correct
5 Correct 82 ms 42056 KB Output is correct
6 Correct 710 ms 281136 KB Output is correct
7 Correct 769 ms 305232 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 5 ms 9676 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 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 9676 KB Output is correct
8 Correct 6 ms 9716 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 10060 KB Output is correct
11 Correct 8 ms 11340 KB Output is correct
12 Correct 36 ms 22284 KB Output is correct
13 Correct 101 ms 63068 KB Output is correct
14 Execution timed out 2079 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 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 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 9676 KB Output is correct
8 Correct 6 ms 9716 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 348 ms 130040 KB Output is correct
11 Execution timed out 2131 ms 1046520 KB Time limit exceeded
12 Halted 0 ms 0 KB -