oj.uz

Submission #1086447

# Submission time Handle Problem Language Result Execution time Memory
1086447 2024-09-10T17:07:07 Z 0x34c Regions (IOI09_regions) C++17
0 / 100
 201 ms 40844 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];
    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;
        }

    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 1 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 0 ms 344 KB Time limit exceeded (wall clock)
4 Execution timed out 0 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 5 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 10 ms 3160 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 21 ms 6744 KB Time limit exceeded (wall clock)
3 Execution timed out 17 ms 10072 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 3160 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 5208 KB Time limit exceeded (wall clock)
6 Execution timed out 22 ms 8708 KB Time limit exceeded (wall clock)
7 Execution timed out 34 ms 11092 KB Time limit exceeded (wall clock)
8 Execution timed out 61 ms 20800 KB Time limit exceeded (wall clock)
9 Execution timed out 36 ms 15444 KB Time limit exceeded (wall clock)
10 Execution timed out 201 ms 40844 KB Time limit exceeded (wall clock)
11 Execution timed out 58 ms 17804 KB Time limit exceeded (wall clock)
12 Execution timed out 92 ms 18360 KB Time limit exceeded (wall clock)
13 Execution timed out 57 ms 18768 KB Time limit exceeded (wall clock)
14 Execution timed out 86 ms 22448 KB Time limit exceeded (wall clock)
15 Execution timed out 44 ms 23456 KB Time limit exceeded (wall clock)
16 Execution timed out 46 ms 28556 KB Time limit exceeded (wall clock)
17 Execution timed out 80 ms 30904 KB Time limit exceeded (wall clock)