oj.uz

Submission #1104949

# Submission time Handle Problem Language Result Execution time Memory
1104949 2024-10-24T21:50:56 Z jerzyk Tree (IOI24_tree) C++17
7 / 100
 118 ms 80580 KB 
#include <bits/stdc++.h>
#include "tree.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int drz[2 * N];
vector<int> aktv;
int pre[N], pos[N], rev[N];

ll wei[N];
ll inc[N * 5], sum[N * 5];
int il[N];
vector<int> ed[N];

void Change(int v, int x)
{
    v += N;
    drz[v] = x;
    v /= 2;
    while(v > 0)
    {
        drz[v] = max(drz[v * 2], drz[v * 2 + 1]);
        v /= 2;
    }
}

void Find(int v, int p, int k, int pz, int kz, int x)
{
    if(drz[v] <= x) return;
    if(p > kz || k < pz) return;
    if(v >= N)
    {
        drz[v] = -1;
        aktv.pb(rev[v - N]);
        return;
    }
    Find(v * 2, p, (p + k) / 2, pz, kz, x);
    Find(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
    drz[v] = max(drz[v * 2], drz[v * 2 + 1]);
}

bool C(int a, int b)
{
    return (wei[a] > wei[b]);
}

void DFS(int v, int &cnt)
{
    ++cnt; rev[cnt] = v; pre[v] = cnt; pos[v] = cnt;
    il[v] = max(0, (int)ed[v].size() - 1);
    Change(pre[v], wei[v]);

    if(ed[v].size() == 0)
        sum[0] += wei[v];
    else
        sum[0] += (ll)il[v] * wei[v];
    //cerr << "DFS: " << v << " " << wei[v] << "\n";

    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        aktv.clear();
        DFS(ed[v][i], cnt);
        pos[v] = pos[ed[v][i]];
        Find(1, 0, N - 1, pre[ed[v][i]], pos[ed[v][i]], wei[v]);
        sort(aktv.begin(), aktv.end(), C);
        int s = 0;
        for(int j = 0; j < (int)aktv.size(); ++j)
        {
            int ne = aktv[j];
            //cout << "R: " << v << " " << ne << "\n";
            inc[1 + s] += wei[v] - wei[ne];
            inc[1 + s + il[ne]] -= wei[v] - wei[ne];
            s += il[ne];
        }
        il[v] += s;
    }
}

void init(vector<int> P, vector<int> W)
{
    for(int i = 1; i < 2 * N; ++i) drz[i] = -1;

    int n = (int)P.size() + 1;
    for(int i = 1; i < (int)P.size(); ++i)
        ed[P[i] + 1].pb(i + 1);
    for(int i = 0; i < n; ++i)
        wei[i + 1] = W[i];
    ed[0].pb(1);
    int xd = 0;
    DFS(0, xd);
    for(int i = 1; i <= 1000'000; ++i)
        inc[i] += inc[i - 1];
    for(int i = 1; i <= 1000'000; ++i)
        sum[i] = sum[i - 1] + inc[i - 1];
}

long long query(int L, int R)
{
    ll ans = sum[R / L] * (ll)L + inc[R / L] * (ll)(R % L);
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34384 KB Output is correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 118 ms 80580 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34640 KB Output is correct
2 Incorrect 11 ms 34384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34640 KB Output is correct
2 Incorrect 11 ms 34384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 55148 KB Output is correct
2 Correct 88 ms 46924 KB Output is correct
3 Correct 83 ms 46960 KB Output is correct
4 Correct 100 ms 47012 KB Output is correct
5 Correct 90 ms 46800 KB Output is correct
6 Correct 79 ms 49076 KB Output is correct
7 Correct 81 ms 46244 KB Output is correct
8 Correct 69 ms 43036 KB Output is correct

Subtask #5
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 55148 KB Output is correct
2 Correct 88 ms 46924 KB Output is correct
3 Correct 83 ms 46960 KB Output is correct
4 Correct 100 ms 47012 KB Output is correct
5 Correct 90 ms 46800 KB Output is correct
6 Correct 79 ms 49076 KB Output is correct
7 Correct 81 ms 46244 KB Output is correct
8 Correct 69 ms 43036 KB Output is correct
9 Incorrect 92 ms 49960 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 54156 KB Output is correct
2 Runtime error 115 ms 76824 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34384 KB Output is correct
2 Runtime error 118 ms 80580 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -