oj.uz

Submission #1086445

# Submission time Handle Problem Language Result Execution time Memory
1086445 2024-09-10T16:51:33 Z 0x34c Regions (IOI09_regions) C++17
0 / 100
 237 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);
}

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 1 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 600 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 1364 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 1368 KB Time limit exceeded (wall clock)
11 Execution timed out 3 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 5 ms 2644 KB Time limit exceeded (wall clock)
14 Execution timed out 7 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 18 ms 6996 KB Time limit exceeded (wall clock)
3 Execution timed out 18 ms 10072 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 3160 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 5116 KB Time limit exceeded (wall clock)
6 Execution timed out 26 ms 8536 KB Time limit exceeded (wall clock)
7 Execution timed out 30 ms 11096 KB Time limit exceeded (wall clock)
8 Execution timed out 67 ms 20816 KB Time limit exceeded (wall clock)
9 Execution timed out 40 ms 15440 KB Time limit exceeded (wall clock)
10 Execution timed out 237 ms 40844 KB Time limit exceeded (wall clock)
11 Execution timed out 54 ms 17640 KB Time limit exceeded (wall clock)
12 Execution timed out 57 ms 18380 KB Time limit exceeded (wall clock)
13 Execution timed out 50 ms 18588 KB Time limit exceeded (wall clock)
14 Execution timed out 84 ms 22448 KB Time limit exceeded (wall clock)
15 Execution timed out 45 ms 23436 KB Time limit exceeded (wall clock)
16 Execution timed out 72 ms 28556 KB Time limit exceeded (wall clock)
17 Execution timed out 90 ms 30640 KB Time limit exceeded (wall clock)