oj.uz

Submission #531420

# Submission time Handle Problem Language Result Execution time Memory
531420 2022-02-28T16:31:47 Z Killer2501 Magic Tree (CEOI19_magictree) C++14
34 / 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, lab[N];
ll ans, tong, d[N], t, a[N], b[N], c[N], dp[N], k;
vector<int> adj[N], radj[N];
vector<pll> vi;
string s, ss;
void add(int& x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
}
map<int, ll> mp[N];
void dfs(int u)
{
    for(int v: adj[u])
    {
        dfs(v);
        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])
    {
        t = a[u];
        while(true)
        {
            auto it = mp[u].upper_bound(b[u]);
            if(it == mp[u].end())break;
            if(t >= (*it).se)
            {
                t -= (*it).se;
                mp[u].erase(it);
            }
            else
            {
                mp[u][(*it).fi] -= t;
                break;
            }

        }
        mp[u][b[u]] += a[u];
    }
    /*
    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);
    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:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         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 7 ms 9664 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 9676 KB Output is correct
7 Correct 5 ms 9648 KB Output is correct
8 Correct 5 ms 9716 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 436 ms 154600 KB Output is correct
2 Runtime error 1957 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 11388 KB Output is correct
3 Correct 46 ms 22348 KB Output is correct
4 Correct 102 ms 62900 KB Output is correct
5 Execution timed out 2122 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 85 ms 22340 KB Output is correct
2 Correct 74 ms 19064 KB Output is correct
3 Correct 76 ms 31940 KB Output is correct
4 Correct 51 ms 24224 KB Output is correct
5 Correct 61 ms 41076 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 7 ms 9664 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 9676 KB Output is correct
7 Correct 5 ms 9648 KB Output is correct
8 Correct 5 ms 9716 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 149 ms 41668 KB Output is correct
11 Correct 115 ms 34020 KB Output is correct
12 Correct 274 ms 141516 KB Output is correct
13 Correct 232 ms 136976 KB Output is correct
14 Correct 258 ms 146256 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12432 KB Output is correct
2 Correct 42 ms 16620 KB Output is correct
3 Correct 38 ms 16340 KB Output is correct
4 Correct 43 ms 17744 KB Output is correct
5 Runtime error 1648 ms 1048580 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

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 7 ms 9664 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 9676 KB Output is correct
7 Correct 5 ms 9648 KB Output is correct
8 Correct 5 ms 9716 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 11388 KB Output is correct
12 Correct 46 ms 22348 KB Output is correct
13 Correct 102 ms 62900 KB Output is correct
14 Execution timed out 2122 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 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 7 ms 9664 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 9676 KB Output is correct
7 Correct 5 ms 9648 KB Output is correct
8 Correct 5 ms 9716 KB Output is correct
9 Correct 5 ms 9716 KB Output is correct
10 Correct 436 ms 154600 KB Output is correct
11 Runtime error 1957 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -