oj.uz

Submission #531426

# Submission time Handle Problem Language Result Execution time Memory
531426 2022-02-28T16:50:33 Z Killer2501 Magic Tree (CEOI19_magictree) C++14
0 / 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];
                nxt = next(it);
                break;
            }
            else
            {
                a[u] -= it->se;
                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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 128792 KB Output is correct
2 Execution timed out 2098 ms 1048580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19780 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 24832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 20632 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -