oj.uz

Submission #1086446

# Submission time Handle Problem Language Result Execution time Memory
1086446 2024-09-10T17:01:05 Z 0x34c Regions (IOI09_regions) C++17
0 / 100
 204 ms 40888 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#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];
    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;
        }

    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])
        {
            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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
9 Execution timed out 1 ms 1112 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 1368 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 1624 KB Time limit exceeded (wall clock)
12 Execution timed out 4 ms 2392 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 2392 KB Time limit exceeded (wall clock)
14 Execution timed out 9 ms 3352 KB Time limit exceeded (wall clock)
15 Execution timed out 9 ms 5976 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 17 ms 7768 KB Time limit exceeded (wall clock)
2 Execution timed out 17 ms 6744 KB Time limit exceeded (wall clock)
3 Execution timed out 25 ms 10072 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 3156 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 5208 KB Time limit exceeded (wall clock)
6 Execution timed out 23 ms 8536 KB Time limit exceeded (wall clock)
7 Execution timed out 29 ms 11096 KB Time limit exceeded (wall clock)
8 Execution timed out 55 ms 20824 KB Time limit exceeded (wall clock)
9 Execution timed out 43 ms 15440 KB Time limit exceeded (wall clock)
10 Execution timed out 204 ms 40888 KB Time limit exceeded (wall clock)
11 Execution timed out 57 ms 17812 KB Time limit exceeded (wall clock)
12 Execution timed out 54 ms 18512 KB Time limit exceeded (wall clock)
13 Execution timed out 58 ms 19140 KB Time limit exceeded (wall clock)
14 Execution timed out 82 ms 22348 KB Time limit exceeded (wall clock)
15 Execution timed out 45 ms 23436 KB Time limit exceeded (wall clock)
16 Execution timed out 49 ms 28556 KB Time limit exceeded (wall clock)
17 Execution timed out 77 ms 30880 KB Time limit exceeded (wall clock)