oj.uz

Submission #531421

# Submission time Handle Problem Language Result Execution time Memory
531421 2022-02-28T16:34:17 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], b[N];
ll ans, tong, d[N], t, a[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(pii 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(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: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 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9680 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 153028 KB Output is correct
2 Runtime error 1986 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 12 ms 11340 KB Output is correct
3 Correct 37 ms 22348 KB Output is correct
4 Correct 100 ms 62132 KB Output is correct
5 Execution timed out 2124 ms 1046628 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 21740 KB Output is correct
2 Correct 74 ms 18612 KB Output is correct
3 Correct 65 ms 31580 KB Output is correct
4 Correct 49 ms 23728 KB Output is correct
5 Correct 66 ms 40616 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 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9680 KB Output is correct
10 Correct 134 ms 41148 KB Output is correct
11 Correct 104 ms 33360 KB Output is correct
12 Correct 275 ms 141044 KB Output is correct
13 Correct 258 ms 136488 KB Output is correct
14 Correct 251 ms 145928 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12260 KB Output is correct
2 Correct 44 ms 16176 KB Output is correct
3 Correct 36 ms 15852 KB Output is correct
4 Correct 44 ms 17156 KB Output is correct
5 Runtime error 1759 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 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9680 KB Output is correct
10 Correct 6 ms 10060 KB Output is correct
11 Correct 12 ms 11340 KB Output is correct
12 Correct 37 ms 22348 KB Output is correct
13 Correct 100 ms 62132 KB Output is correct
14 Execution timed out 2124 ms 1046628 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 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9668 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9680 KB Output is correct
10 Correct 412 ms 153028 KB Output is correct
11 Runtime error 1986 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -