oj.uz

Submission #531437

# Submission time Handle Problem Language Result Execution time Memory
531437 2022-02-28T17:00:03 Z Killer2501 Magic Tree (CEOI19_magictree) C++17
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(ll v = 0; it != mp[u].end(); it = nxt)
        {
            v += it->se;
            if(v <= a[u])
            {
                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:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 8 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9712 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 353 ms 129120 KB Output is correct
2 Runtime error 1946 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 38 ms 22344 KB Output is correct
4 Correct 106 ms 62924 KB Output is correct
5 Execution timed out 2064 ms 1005784 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 21632 KB Output is correct
2 Correct 83 ms 18460 KB Output is correct
3 Correct 75 ms 31308 KB Output is correct
4 Correct 52 ms 22552 KB Output is correct
5 Correct 71 ms 40668 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 8 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 130 ms 40456 KB Output is correct
11 Correct 114 ms 32984 KB Output is correct
12 Correct 265 ms 138576 KB Output is correct
13 Correct 220 ms 124012 KB Output is correct
14 Correct 269 ms 145960 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11212 KB Output is correct
2 Correct 45 ms 13860 KB Output is correct
3 Correct 36 ms 13892 KB Output is correct
4 Correct 37 ms 14540 KB Output is correct
5 Correct 81 ms 42244 KB Output is correct
6 Correct 706 ms 281296 KB Output is correct
7 Correct 684 ms 305588 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 8 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9712 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 38 ms 22344 KB Output is correct
13 Correct 106 ms 62924 KB Output is correct
14 Execution timed out 2064 ms 1005784 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 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 8 ms 9720 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9712 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 353 ms 129120 KB Output is correct
11 Runtime error 1946 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -