oj.uz

Submission #672737

# Submission time Handle Problem Language Result Execution time Memory
672737 2022-12-17T21:36:22 Z finn__ Regions (IOI09_regions) C++17
100 / 100
 4192 ms 42692 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<unsigned>> g;
vector<unsigned> h, y, z;

unsigned preorder(unsigned u, unsigned p, unsigned i = 0)
{
    y[u] = i++;
    for (unsigned v : g[u])
        if (v != p)
            i = preorder(v, u, i);
    z[u] = i;
    return i;
}

struct interval
{
    unsigned i, j, v;
};

void buidl_intv(
    unsigned u, unsigned p, vector<vector<interval>> &intv,
    vector<unsigned> &reg_end, vector<unsigned> &num_reg)
{
    if (y[u])
    {
        intv[h[u]].push_back({reg_end[h[u]], y[u] - 1, num_reg[h[u]]});
        reg_end[h[u]] = y[u];
    }
    num_reg[h[u]]++;

    for (unsigned v : g[u])
        if (v != p)
            buidl_intv(v, u, intv, reg_end, num_reg);

    intv[h[u]].push_back({reg_end[h[u]], z[u] - 1, num_reg[h[u]]});
    reg_end[h[u]] = z[u];
    num_reg[h[u]]--;
}

int main()
{
    size_t n, r, q;
    cin >> n >> r >> q;

    g = vector<vector<unsigned>>(n);
    h = vector<unsigned>(n);
    cin >> h[0];
    h[0]--;

    for (unsigned u = 1; u < n; u++)
    {
        unsigned v;
        cin >> v >> h[u];
        h[u]--;
        g[u].push_back(v - 1);
        g[v - 1].push_back(u);
    }

    y = vector<unsigned>(n);
    z = vector<unsigned>(n);
    assert(preorder(0, -1) == n);

    vector<vector<unsigned>> reg(r);

    for (unsigned i = 0; i < n; i++)
        reg[h[i]].push_back(y[i]);
    for (vector<unsigned> &v : reg)
        sort(v.begin(), v.end());

    vector<vector<interval>> intv(r);
    vector<unsigned> reg_end(r, 0), num_reg(r, 0);
    buidl_intv(0, -1, intv, reg_end, num_reg);

    for (size_t i = 0; i < q; i++)
    {
        unsigned r1, r2;
        cin >> r1 >> r2;
        r1--, r2--;

        auto it = intv[r1].begin();
        auto jt = reg[r2].begin();
        unsigned total = 0;

        while (it != intv[r1].end() && jt != reg[r2].end())
        {
            if (*jt < it->i)
                jt++;
            else if (it->j < *jt)
                it++;
            else if (it->i <= *jt && *jt <= it->j)
            {
                total += it->v;
                jt++;
            }
        }

        cout << total << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 17 ms 464 KB Output is correct
7 Correct 26 ms 464 KB Output is correct
8 Correct 27 ms 464 KB Output is correct
9 Correct 38 ms 1360 KB Output is correct
10 Correct 70 ms 1360 KB Output is correct
11 Correct 88 ms 2000 KB Output is correct
12 Correct 116 ms 2972 KB Output is correct
13 Correct 142 ms 3192 KB Output is correct
14 Correct 186 ms 3804 KB Output is correct
15 Correct 199 ms 9292 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2445 ms 9664 KB Output is correct
2 Correct 3740 ms 8888 KB Output is correct
3 Correct 4192 ms 13256 KB Output is correct
4 Correct 236 ms 4120 KB Output is correct
5 Correct 291 ms 7324 KB Output is correct
6 Correct 689 ms 6728 KB Output is correct
7 Correct 965 ms 9128 KB Output is correct
8 Correct 787 ms 18724 KB Output is correct
9 Correct 1325 ms 20432 KB Output is correct
10 Correct 1898 ms 29560 KB Output is correct
11 Correct 2093 ms 23880 KB Output is correct
12 Correct 1926 ms 21152 KB Output is correct
13 Correct 2252 ms 22936 KB Output is correct
14 Correct 2777 ms 23340 KB Output is correct
15 Correct 3111 ms 30684 KB Output is correct
16 Correct 3293 ms 42692 KB Output is correct
17 Correct 3778 ms 40848 KB Output is correct