oj.uz

Submission #1086451

# Submission time Handle Problem Language Result Execution time Memory
1086451 2024-09-10T17:19:01 Z 0x34c Regions (IOI09_regions) C++
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 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 0 ms 344 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 596 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 1112 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 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 7 ms 3160 KB Time limit exceeded (wall clock)
15 Execution timed out 8 ms 5976 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18 ms 7768 KB Time limit exceeded (wall clock)
2 Execution timed out 18 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 8 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 23 ms 8536 KB Time limit exceeded (wall clock)
7 Execution timed out 37 ms 11096 KB Time limit exceeded (wall clock)
8 Execution timed out 61 ms 20816 KB Time limit exceeded (wall clock)
9 Execution timed out 39 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 53 ms 17804 KB Time limit exceeded (wall clock)
12 Execution timed out 56 ms 18512 KB Time limit exceeded (wall clock)
13 Execution timed out 47 ms 18600 KB Time limit exceeded (wall clock)
14 Execution timed out 78 ms 22448 KB Time limit exceeded (wall clock)
15 Execution timed out 43 ms 23688 KB Time limit exceeded (wall clock)
16 Execution timed out 47 ms 28540 KB Time limit exceeded (wall clock)
17 Execution timed out 76 ms 30904 KB Time limit exceeded (wall clock)