oj.uz

Submission #531419

# Submission time Handle Problem Language Result Execution time Memory
531419 2022-02-28T16:30:03 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 = 1e6+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(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(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 47 ms 94276 KB Output is correct
2 Correct 45 ms 94240 KB Output is correct
3 Correct 44 ms 94244 KB Output is correct
4 Correct 44 ms 94228 KB Output is correct
5 Correct 45 ms 94196 KB Output is correct
6 Correct 48 ms 94276 KB Output is correct
7 Correct 43 ms 94288 KB Output is correct
8 Correct 44 ms 94268 KB Output is correct
9 Correct 44 ms 94188 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 239044 KB Output is correct
2 Runtime error 1881 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 49 ms 94668 KB Output is correct
2 Correct 67 ms 95956 KB Output is correct
3 Correct 97 ms 106932 KB Output is correct
4 Correct 151 ms 149032 KB Output is correct
5 Execution timed out 2029 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 145 ms 108828 KB Output is correct
2 Correct 136 ms 105584 KB Output is correct
3 Correct 125 ms 118636 KB Output is correct
4 Correct 99 ms 110508 KB Output is correct
5 Correct 121 ms 127708 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94276 KB Output is correct
2 Correct 45 ms 94240 KB Output is correct
3 Correct 44 ms 94244 KB Output is correct
4 Correct 44 ms 94228 KB Output is correct
5 Correct 45 ms 94196 KB Output is correct
6 Correct 48 ms 94276 KB Output is correct
7 Correct 43 ms 94288 KB Output is correct
8 Correct 44 ms 94268 KB Output is correct
9 Correct 44 ms 94188 KB Output is correct
10 Correct 186 ms 127744 KB Output is correct
11 Correct 166 ms 119752 KB Output is correct
12 Correct 319 ms 227520 KB Output is correct
13 Correct 272 ms 222496 KB Output is correct
14 Correct 289 ms 232304 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 96936 KB Output is correct
2 Correct 88 ms 101668 KB Output is correct
3 Correct 83 ms 101288 KB Output is correct
4 Correct 93 ms 102712 KB Output is correct
5 Runtime error 1607 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 47 ms 94276 KB Output is correct
2 Correct 45 ms 94240 KB Output is correct
3 Correct 44 ms 94244 KB Output is correct
4 Correct 44 ms 94228 KB Output is correct
5 Correct 45 ms 94196 KB Output is correct
6 Correct 48 ms 94276 KB Output is correct
7 Correct 43 ms 94288 KB Output is correct
8 Correct 44 ms 94268 KB Output is correct
9 Correct 44 ms 94188 KB Output is correct
10 Correct 49 ms 94668 KB Output is correct
11 Correct 67 ms 95956 KB Output is correct
12 Correct 97 ms 106932 KB Output is correct
13 Correct 151 ms 149032 KB Output is correct
14 Execution timed out 2029 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 47 ms 94276 KB Output is correct
2 Correct 45 ms 94240 KB Output is correct
3 Correct 44 ms 94244 KB Output is correct
4 Correct 44 ms 94228 KB Output is correct
5 Correct 45 ms 94196 KB Output is correct
6 Correct 48 ms 94276 KB Output is correct
7 Correct 43 ms 94288 KB Output is correct
8 Correct 44 ms 94268 KB Output is correct
9 Correct 44 ms 94188 KB Output is correct
10 Correct 490 ms 239044 KB Output is correct
11 Runtime error 1881 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -