oj.uz

Submission #1086478

# Submission time Handle Problem Language Result Execution time Memory
1086478 2024-09-10T18:23:24 Z 0x34c Regions (IOI09_regions) C++17
0 / 100
 105 ms 32848 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;
const int MAX_N = 2e5 + 1;
const int MX_SQRT = 448;
const int MAX_R = 25001;
vector<int> graph[MAX_N], rgraph[MAX_N];
int sol[MX_SQRT][MAX_R];
int regions[MAX_N], reg_cnt[MAX_R], conv[MAX_R], tin[MAX_N], tout[MAX_N], cnt[MAX_R];
vector<int> sqrt_r;

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);

    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;
        }
        else
            conv[i] = -1;
    }

    int tim = 0;
    etour(0, tim);
    dfs(0);

    for (int _ = 0; _ < 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;

            int amt = 0;
            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;
            amt = 0;
            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;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:94:17: warning: variable 'amt' set but not used [-Wunused-but-set-variable]
   94 |             int amt = 0;
      |                 ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
3 Execution timed out 5 ms 9816 KB Time limit exceeded (wall clock)
4 Execution timed out 5 ms 9816 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 9816 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 10328 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 10328 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 10836 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 10840 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 10580 KB Time limit exceeded (wall clock)
14 Execution timed out 10 ms 11096 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 13656 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 22 ms 14168 KB Time limit exceeded (wall clock)
2 Execution timed out 21 ms 12888 KB Time limit exceeded (wall clock)
3 Execution timed out 23 ms 15700 KB Time limit exceeded (wall clock)
4 Execution timed out 11 ms 11352 KB Time limit exceeded (wall clock)
5 Execution timed out 11 ms 12888 KB Time limit exceeded (wall clock)
6 Execution timed out 20 ms 14168 KB Time limit exceeded (wall clock)
7 Execution timed out 34 ms 15568 KB Time limit exceeded (wall clock)
8 Execution timed out 49 ms 22360 KB Time limit exceeded (wall clock)
9 Execution timed out 35 ms 18256 KB Time limit exceeded (wall clock)
10 Execution timed out 105 ms 32848 KB Time limit exceeded (wall clock)
11 Execution timed out 67 ms 17744 KB Time limit exceeded (wall clock)
12 Execution timed out 51 ms 19536 KB Time limit exceeded (wall clock)
13 Execution timed out 43 ms 20044 KB Time limit exceeded (wall clock)
14 Execution timed out 65 ms 21072 KB Time limit exceeded (wall clock)
15 Execution timed out 46 ms 23888 KB Time limit exceeded (wall clock)
16 Execution timed out 48 ms 29096 KB Time limit exceeded (wall clock)
17 Execution timed out 52 ms 29580 KB Time limit exceeded (wall clock)