oj.uz

Submission #1095603

# Submission time Handle Problem Language Result Execution time Memory
1095603 2024-10-02T16:29:51 Z cpptowin Magic Tree (CEOI19_magictree) C++17
100 / 100
 133 ms 101716 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcout(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    if (x >= mod)
        x -= mod;
}
map<int, int> f[maxn];
int d[maxn], w[maxn];
vi ke[maxn];
int n, m, k;
void dfs(int u, int par = 0)
{
    for (int v : ke[u])
        if (v != par)
        {
            dfs(v, u);
            if (ss(f[u]) < ss(f[v]))
                swap(f[u], f[v]);
            for (auto it : f[v])
                f[u][it.fi] += it.se;
        }
    if (d[u] and w[u])
    {
        int sum = 0;
        while (1)
        {
            auto ub = f[u].upper_bound(d[u]);
            if (ub == f[u].end())
                break;
            if (sum + ub->se < w[u])
            {
                sum += ub->se;
                f[u].erase(ub);
            }
            else
            {
                ub->se += sum - w[u];
                break;
            }
        }
        f[u][d[u]] += w[u];
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k;
    fo(i, 1, n) ke[i].clear();
    fo(i, 2, n)
    {
        int x;
        cin >> x;
        ke[x].pb(i);
    }
    fo(i, 1, m)
    {
        int u;
        cin >> u >> d[u] >> w[u];
    }
    dfs(1);
    int ans = 0;
    for (auto it : f[1])
        ans += it.se;
    cout << ans;
    en;
}

Compilation message

magictree.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main()
      | ^~~~
magictree.cpp: In function 'int main()':
magictree.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70744 KB Output is correct
2 Correct 30 ms 70744 KB Output is correct
3 Correct 28 ms 70656 KB Output is correct
4 Correct 28 ms 70860 KB Output is correct
5 Correct 30 ms 70824 KB Output is correct
6 Correct 30 ms 70748 KB Output is correct
7 Correct 27 ms 70740 KB Output is correct
8 Correct 27 ms 70736 KB Output is correct
9 Correct 27 ms 70736 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 83028 KB Output is correct
2 Correct 57 ms 83844 KB Output is correct
3 Correct 133 ms 101716 KB Output is correct
4 Correct 77 ms 84492 KB Output is correct
5 Correct 100 ms 86864 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70916 KB Output is correct
2 Correct 28 ms 70992 KB Output is correct
3 Correct 29 ms 70916 KB Output is correct
4 Correct 72 ms 93008 KB Output is correct
5 Correct 83 ms 96912 KB Output is correct
6 Correct 77 ms 93216 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 79952 KB Output is correct
2 Correct 71 ms 79288 KB Output is correct
3 Correct 68 ms 84472 KB Output is correct
4 Correct 54 ms 80512 KB Output is correct
5 Correct 60 ms 93324 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70744 KB Output is correct
2 Correct 30 ms 70744 KB Output is correct
3 Correct 28 ms 70656 KB Output is correct
4 Correct 28 ms 70860 KB Output is correct
5 Correct 30 ms 70824 KB Output is correct
6 Correct 30 ms 70748 KB Output is correct
7 Correct 27 ms 70740 KB Output is correct
8 Correct 27 ms 70736 KB Output is correct
9 Correct 27 ms 70736 KB Output is correct
10 Correct 75 ms 83464 KB Output is correct
11 Correct 78 ms 82172 KB Output is correct
12 Correct 59 ms 83796 KB Output is correct
13 Correct 53 ms 79820 KB Output is correct
14 Correct 60 ms 92500 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 71760 KB Output is correct
2 Correct 43 ms 74832 KB Output is correct
3 Correct 49 ms 74832 KB Output is correct
4 Correct 47 ms 75088 KB Output is correct
5 Correct 33 ms 73420 KB Output is correct
6 Correct 46 ms 77960 KB Output is correct
7 Correct 44 ms 81748 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70744 KB Output is correct
2 Correct 30 ms 70744 KB Output is correct
3 Correct 28 ms 70656 KB Output is correct
4 Correct 28 ms 70860 KB Output is correct
5 Correct 30 ms 70824 KB Output is correct
6 Correct 30 ms 70748 KB Output is correct
7 Correct 27 ms 70740 KB Output is correct
8 Correct 27 ms 70736 KB Output is correct
9 Correct 27 ms 70736 KB Output is correct
10 Correct 28 ms 70916 KB Output is correct
11 Correct 28 ms 70992 KB Output is correct
12 Correct 29 ms 70916 KB Output is correct
13 Correct 72 ms 93008 KB Output is correct
14 Correct 83 ms 96912 KB Output is correct
15 Correct 77 ms 93216 KB Output is correct
16 Correct 75 ms 83464 KB Output is correct
17 Correct 78 ms 82172 KB Output is correct
18 Correct 59 ms 83796 KB Output is correct
19 Correct 53 ms 79820 KB Output is correct
20 Correct 60 ms 92500 KB Output is correct
21 Correct 46 ms 75088 KB Output is correct
22 Correct 73 ms 84812 KB Output is correct
23 Correct 92 ms 89168 KB Output is correct
24 Correct 126 ms 100692 KB Output is correct
25 Correct 82 ms 83920 KB Output is correct
26 Correct 101 ms 87064 KB Output is correct
27 Correct 86 ms 86592 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 70744 KB Output is correct
2 Correct 30 ms 70744 KB Output is correct
3 Correct 28 ms 70656 KB Output is correct
4 Correct 28 ms 70860 KB Output is correct
5 Correct 30 ms 70824 KB Output is correct
6 Correct 30 ms 70748 KB Output is correct
7 Correct 27 ms 70740 KB Output is correct
8 Correct 27 ms 70736 KB Output is correct
9 Correct 27 ms 70736 KB Output is correct
10 Correct 70 ms 83028 KB Output is correct
11 Correct 57 ms 83844 KB Output is correct
12 Correct 133 ms 101716 KB Output is correct
13 Correct 77 ms 84492 KB Output is correct
14 Correct 100 ms 86864 KB Output is correct
15 Correct 28 ms 70916 KB Output is correct
16 Correct 28 ms 70992 KB Output is correct
17 Correct 29 ms 70916 KB Output is correct
18 Correct 72 ms 93008 KB Output is correct
19 Correct 83 ms 96912 KB Output is correct
20 Correct 77 ms 93216 KB Output is correct
21 Correct 69 ms 79952 KB Output is correct
22 Correct 71 ms 79288 KB Output is correct
23 Correct 68 ms 84472 KB Output is correct
24 Correct 54 ms 80512 KB Output is correct
25 Correct 60 ms 93324 KB Output is correct
26 Correct 75 ms 83464 KB Output is correct
27 Correct 78 ms 82172 KB Output is correct
28 Correct 59 ms 83796 KB Output is correct
29 Correct 53 ms 79820 KB Output is correct
30 Correct 60 ms 92500 KB Output is correct
31 Correct 31 ms 71760 KB Output is correct
32 Correct 43 ms 74832 KB Output is correct
33 Correct 49 ms 74832 KB Output is correct
34 Correct 47 ms 75088 KB Output is correct
35 Correct 33 ms 73420 KB Output is correct
36 Correct 46 ms 77960 KB Output is correct
37 Correct 44 ms 81748 KB Output is correct
38 Correct 46 ms 75088 KB Output is correct
39 Correct 73 ms 84812 KB Output is correct
40 Correct 92 ms 89168 KB Output is correct
41 Correct 126 ms 100692 KB Output is correct
42 Correct 82 ms 83920 KB Output is correct
43 Correct 101 ms 87064 KB Output is correct
44 Correct 86 ms 86592 KB Output is correct
45 Correct 40 ms 74832 KB Output is correct
46 Correct 80 ms 84308 KB Output is correct
47 Correct 91 ms 87732 KB Output is correct
48 Correct 117 ms 97892 KB Output is correct
49 Correct 78 ms 84684 KB Output is correct
50 Correct 92 ms 87352 KB Output is correct
51 Correct 88 ms 86540 KB Output is correct