oj.uz

Submission #1086487

# Submission time Handle Problem Language Result Execution time Memory
1086487 2024-09-10T18:35:24 Z 0x34c Regions (IOI09_regions) C++17
0 / 100
 101 ms 27984 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'

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
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 0 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 0 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 2 ms 856 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 1112 KB Time limit exceeded (wall clock)
11 Execution timed out 3 ms 1368 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 1912 KB Time limit exceeded (wall clock)
13 Execution timed out 5 ms 1880 KB Time limit exceeded (wall clock)
14 Execution timed out 6 ms 2392 KB Time limit exceeded (wall clock)
15 Execution timed out 8 ms 5208 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 19 ms 6488 KB Time limit exceeded (wall clock)
2 Execution timed out 18 ms 5208 KB Time limit exceeded (wall clock)
3 Execution timed out 18 ms 8536 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 2648 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 4440 KB Time limit exceeded (wall clock)
6 Execution timed out 32 ms 5976 KB Time limit exceeded (wall clock)
7 Execution timed out 27 ms 7768 KB Time limit exceeded (wall clock)
8 Execution timed out 49 ms 15192 KB Time limit exceeded (wall clock)
9 Execution timed out 34 ms 12632 KB Time limit exceeded (wall clock)
10 Execution timed out 101 ms 27984 KB Time limit exceeded (wall clock)
11 Execution timed out 51 ms 13648 KB Time limit exceeded (wall clock)
12 Execution timed out 52 ms 14928 KB Time limit exceeded (wall clock)
13 Execution timed out 44 ms 15184 KB Time limit exceeded (wall clock)
14 Execution timed out 65 ms 16716 KB Time limit exceeded (wall clock)
15 Execution timed out 43 ms 19536 KB Time limit exceeded (wall clock)
16 Execution timed out 52 ms 25168 KB Time limit exceeded (wall clock)
17 Execution timed out 58 ms 25424 KB Time limit exceeded (wall clock)