oj.uz

Submission #1086492

# Submission time Handle Problem Language Result Execution time Memory
1086492 2024-09-10T18:47:07 Z 0x34c Regions (IOI09_regions) C++17
100 / 100
 2736 ms 40916 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define int ll

using namespace std;

int N, R, Q, SQRT_N;
vector<vector<int>> graph, sol, rgraph;
vector<int> regions, reg_cnt, sqrt_r, conv, tin, tout;

vector<int> cnt;
void dfs(int v)
{
    for (int r : sqrt_r)
        sol[conv[r]][regions[v]] += cnt[r];
    cnt[regions[v]]++;

    for (int u : graph[v])
        dfs(u);
    cnt[regions[v]]--;
}

void etour(int v, int &tim)
{
    rgraph[regions[v]].push_back(v);
    tin[v] = tim++;
    for (int u : graph[v])
        etour(u, tim);
    tout[v] = tim++;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> R >> Q;
    SQRT_N = sqrt(N);
    graph = vector<vector<int>>(N);
    regions = vector<int>(N, -1);
    reg_cnt = vector<int>(R, 0);
    conv = vector<int>(R, -1);
    cnt = vector<int>(R, 0);
    tin = vector<int>(N);
    tout = vector<int>(N);
    rgraph = vector<vector<int>>(R);

    cin >> regions[0];
    --regions[0];
    reg_cnt[regions[0]]++;
    for (int i = 1; i < N; i++)
    {
        int v;
        cin >> v >> regions[i];
        --regions[i];
        --v;
        graph[v].push_back(i);
        reg_cnt[regions[i]]++;
    }

    for (int i = 0; i < R; i++)
        if (reg_cnt[i] > SQRT_N)
        {
            sqrt_r.push_back(i);
            conv[i] = sqrt_r.size() - 1;
        }

    if (!sqrt_r.empty())
        sol = vector<vector<int>>(sqrt_r.size(), vector<int>(R, 0));
    int tim = 0;
    etour(0, tim);
    dfs(0);

    while (Q--)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;

        if (conv[a] != -1)
        {
            cout << sol[conv[a]][b] << endl;
            continue;
        }

        int res = 0;
        for (int v : rgraph[a])
        {
            if (rgraph[b].empty())
                continue;
            int l = 0, r = rgraph[b].size() - 1;
            int lb = -1;
            while (l <= r)
            {
                int m = l + (r - l) / 2;
                int u = rgraph[b][m];
                if (tin[u] < tin[v])
                    l = m + 1;
                else if (tout[u] > tout[v])
                    r = m - 1;
                else
                {
                    lb = m;
                    r = m - 1;
                }
            }

            if (lb == -1)
                continue;
            l = 0;
            r = rgraph[b].size() - 1;
            int rb = -1;
            while (l <= r)
            {
                int m = l + (r - l) / 2;
                int u = rgraph[b][m];
                if (tin[u] < tin[v])
                    l = m + 1;
                else if (tout[u] > tout[v])
                    r = m - 1;
                else
                {
                    rb = m;
                    l = m + 1;
                }
            }

            res += (rb - lb + 1);
        }
        cout << res << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 16 ms 600 KB Output is correct
8 Correct 12 ms 600 KB Output is correct
9 Correct 21 ms 1112 KB Output is correct
10 Correct 43 ms 1368 KB Output is correct
11 Correct 80 ms 1624 KB Output is correct
12 Correct 83 ms 2508 KB Output is correct
13 Correct 114 ms 2412 KB Output is correct
14 Correct 150 ms 3172 KB Output is correct
15 Correct 227 ms 6056 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1632 ms 7824 KB Output is correct
2 Correct 1613 ms 6948 KB Output is correct
3 Correct 2479 ms 10160 KB Output is correct
4 Correct 171 ms 3348 KB Output is correct
5 Correct 232 ms 5224 KB Output is correct
6 Correct 401 ms 8776 KB Output is correct
7 Correct 830 ms 11164 KB Output is correct
8 Correct 786 ms 20960 KB Output is correct
9 Correct 1661 ms 15672 KB Output is correct
10 Correct 2510 ms 40916 KB Output is correct
11 Correct 2736 ms 17852 KB Output is correct
12 Correct 1006 ms 18536 KB Output is correct
13 Correct 1498 ms 18812 KB Output is correct
14 Correct 1658 ms 22476 KB Output is correct
15 Correct 2611 ms 23572 KB Output is correct
16 Correct 2655 ms 28664 KB Output is correct
17 Correct 2417 ms 30892 KB Output is correct