oj.uz

Submission #1086488

# Submission time Handle Problem Language Result Execution time Memory
1086488 2024-09-10T18:35:53 Z 0x34c Regions (IOI09_regions) C++17
33 / 100
 2723 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[conv[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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 14 ms 600 KB Output is correct
8 Correct 11 ms 600 KB Output is correct
9 Correct 26 ms 1112 KB Output is correct
10 Correct 49 ms 1368 KB Output is correct
11 Correct 84 ms 1624 KB Output is correct
12 Correct 99 ms 2392 KB Output is correct
13 Correct 98 ms 2412 KB Output is correct
14 Incorrect 149 ms 3188 KB Output isn't correct
15 Incorrect 205 ms 6072 KB Output isn't correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1558 ms 7828 KB Output isn't correct
2 Incorrect 1692 ms 6948 KB Output isn't correct
3 Incorrect 2427 ms 10152 KB Output isn't correct
4 Correct 170 ms 3432 KB Output is correct
5 Correct 259 ms 5456 KB Output is correct
6 Incorrect 399 ms 8760 KB Output isn't correct
7 Incorrect 834 ms 11168 KB Output isn't correct
8 Incorrect 763 ms 20960 KB Output isn't correct
9 Correct 1679 ms 15672 KB Output is correct
10 Incorrect 2435 ms 40916 KB Output isn't correct
11 Correct 2723 ms 17856 KB Output is correct
12 Incorrect 979 ms 18536 KB Output isn't correct
13 Incorrect 1477 ms 18816 KB Output isn't correct
14 Incorrect 1602 ms 22472 KB Output isn't correct
15 Incorrect 2515 ms 23576 KB Output isn't correct
16 Incorrect 2625 ms 28668 KB Output isn't correct
17 Incorrect 2432 ms 30888 KB Output isn't correct