oj.uz

Submission #1086486

# Submission time Handle Problem Language Result Execution time Memory
1086486 2024-09-10T18:34:04 Z 0x34c Regions (IOI09_regions) C++17
2 / 100
 3701 ms 45616 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define int ll

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)
{
    tin[v] = tim++;
    rgraph[regions[v]].push_back(tin[v]);
    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;
            res += lower_bound(rgraph[b].begin(), rgraph[b].end(), tout[v]) - lower_bound(rgraph[b].begin(), rgraph[b].end(), tin[v]);
        }
        cout << res << endl;
    }
}

Subtask #1
2.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9816 KB Output isn't correct
2 Incorrect 4 ms 9816 KB Output isn't correct
3 Incorrect 4 ms 9816 KB Output isn't correct
4 Incorrect 6 ms 9816 KB Output isn't correct
5 Incorrect 8 ms 9816 KB Output isn't correct
6 Correct 13 ms 9816 KB Output is correct
7 Incorrect 17 ms 9816 KB Output isn't correct
8 Incorrect 22 ms 9816 KB Output isn't correct
9 Correct 25 ms 10436 KB Output is correct
10 Incorrect 61 ms 10328 KB Output isn't correct
11 Incorrect 77 ms 10840 KB Output isn't correct
12 Incorrect 87 ms 11444 KB Output isn't correct
13 Incorrect 117 ms 11272 KB Output isn't correct
14 Incorrect 165 ms 11888 KB Output isn't correct
15 Incorrect 225 ms 14424 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1154 ms 15556 KB Output isn't correct
2 Incorrect 1276 ms 14536 KB Output isn't correct
3 Incorrect 1893 ms 17240 KB Output isn't correct
4 Incorrect 192 ms 11964 KB Output isn't correct
5 Incorrect 258 ms 13656 KB Output isn't correct
6 Incorrect 363 ms 16984 KB Output isn't correct
7 Incorrect 734 ms 18776 KB Output isn't correct
8 Incorrect 723 ms 27992 KB Output isn't correct
9 Incorrect 1794 ms 21208 KB Output isn't correct
10 Incorrect 2196 ms 45616 KB Output isn't correct
11 Incorrect 3701 ms 21952 KB Output isn't correct
12 Incorrect 1129 ms 23120 KB Output isn't correct
13 Incorrect 1502 ms 23380 KB Output isn't correct
14 Incorrect 1796 ms 26536 KB Output isn't correct
15 Incorrect 2719 ms 27528 KB Output isn't correct
16 Incorrect 2588 ms 32780 KB Output isn't correct
17 Incorrect 2484 ms 35120 KB Output isn't correct