oj.uz

Submission #1099833

# Submission time Handle Problem Language Result Execution time Memory
1099833 2024-10-12T05:32:20 Z model_code Tree (IOI24_tree) C++17
13 / 100
 1132 ms 2097152 KB 
// time_limit/kian-vss-qn2h-nl.cpp

// Problem: Tree
// Solution: very simple & slow, no leaves
// Time: n^2 * log(n) + q * n^2 * h
//  (h = tree height)
// Author: Kian Mirjalali

#include "tree.h"
#include <algorithm>
#include <iostream>
using namespace std;


#define allOf(c) (std::begin(c)), (std::end(c))
#define fori(i, a, b) for (int i = (a); (i < (b)); i++)
#define forn(i, n) fori(i, 0, n)
#define forv(i, v) forn(i, sz(v))
#define forRev(i, b, a) for (int i = ((b)-1); (i >= (a)); i--)

template<class C>
int sz(const C& c) {
    return c.size();
}

template<class A, class B>
bool minEq(A& a, const B& b) {
    return (b < a) && ((a = b), true);
}


template<class C1, class C2>
void append(C1& c1, const C2& c2) {
    c1.insert(std::end(c1), allOf(c2));
}


using Long = long long;
using VI = vector<int>;

int n;
VI p, w;

vector<VI> children;
vector<VI> subWSort;

bool wComp(int i, int j) {
    return w[i] < w[j];
}

void init(VI P, VI W) {
    p = P;
    w = W;
    n = p.size();
    children.assign(n, VI());
    fori(i, 1, n)
        children[p[i]].push_back(i);
    subWSort.assign(n, VI());
    // cerr << "B_init" << endl;
    forRev(u, n, 0) {
        if (children[u].empty())
            continue;
        auto& ws = subWSort[u];
        ws.push_back(u);
        for (int child : children[u])
            append(ws, subWSort[child]);
    }
    // cerr << "M_init" << endl;
    for (auto& ws : subWSort)
        sort(allOf(ws), wComp);
    // cerr << "EO_init" << endl;
}

Long query(int L, int R) {
    if (L*(long long)R <= 0) return 0;
    if (L < 0) return query(-R, -L);
    vector<Long> coef(n), subCSum(n);
    forRev(u, n, 0) {
        if (children[u].empty()) {
            subCSum[u] = coef[u] = L;
            continue;
        }
        subCSum[u] = coef[u] = 0;
        for (int child : children[u])
            subCSum[u] += subCSum[child];
        for (int v : subWSort[u]) {
            if (subCSum[u] <= R)
                break;
            Long d = subCSum[u]-R;
            // d > 0
            for (int x = v; x != p[u]; x = p[x])
                minEq(d, subCSum[x]-L);
            coef[v] -= d;
            for (int x = v; x != p[u]; x = p[x])
                subCSum[x] -= d;
        }
    }

    Long cost = 0;
    forn(i, n)
        cost += abs(coef[i])*w[i];
    return cost;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 954 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 3420 KB Output is correct
2 Correct 21 ms 1040 KB Output is correct
3 Correct 40 ms 856 KB Output is correct
4 Correct 14 ms 860 KB Output is correct
5 Correct 13 ms 872 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 3420 KB Output is correct
2 Correct 21 ms 1040 KB Output is correct
3 Correct 40 ms 856 KB Output is correct
4 Correct 14 ms 860 KB Output is correct
5 Correct 13 ms 872 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Runtime error 797 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1132 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1132 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1095 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 954 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -