oj.uz

Submission #531436

# Submission time Handle Problem Language Result Execution time Memory
531436 2022-02-28T16:59:35 Z Killer2501 Magic Tree (CEOI19_magictree) C++17
12 / 100
 1982 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(ll v = 0; it != mp[u].end(); it = nxt)
        {
            v += it->se;
            if(v <= a[u])
            {
                v -= it->se;
                nxt = next(it);
                mp[u].erase(it);
            }
            else
            {
                it->se = v-a[u];
                break;
            }
        }
    }
    /*
    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 129040 KB Output is correct
2 Runtime error 1982 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 Incorrect 6 ms 9932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 21464 KB Output is correct
2 Correct 90 ms 18432 KB Output is correct
3 Correct 72 ms 31272 KB Output is correct
4 Correct 51 ms 22524 KB Output is correct
5 Correct 69 ms 40528 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -