oj.uz

Submission #1086485

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

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 6 ms 9816 KB Output isn't correct
2 Incorrect 4 ms 9828 KB Output isn't correct
3 Incorrect 5 ms 9816 KB Output isn't correct
4 Incorrect 6 ms 9816 KB Output isn't correct
5 Incorrect 7 ms 9816 KB Output isn't correct
6 Correct 14 ms 9816 KB Output is correct
7 Incorrect 18 ms 9816 KB Output isn't correct
8 Incorrect 22 ms 9816 KB Output isn't correct
9 Correct 28 ms 10328 KB Output is correct
10 Incorrect 52 ms 10328 KB Output isn't correct
11 Incorrect 77 ms 10584 KB Output isn't correct
12 Incorrect 95 ms 10840 KB Output isn't correct
13 Incorrect 138 ms 10584 KB Output isn't correct
14 Incorrect 156 ms 11096 KB Output isn't correct
15 Incorrect 198 ms 13908 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1135 ms 14236 KB Output isn't correct
2 Incorrect 1289 ms 13172 KB Output isn't correct
3 Incorrect 1986 ms 15912 KB Output isn't correct
4 Incorrect 190 ms 11352 KB Output isn't correct
5 Incorrect 248 ms 12888 KB Output isn't correct
6 Incorrect 359 ms 14168 KB Output isn't correct
7 Incorrect 791 ms 15448 KB Output isn't correct
8 Incorrect 712 ms 22352 KB Output isn't correct
9 Incorrect 1797 ms 18264 KB Output isn't correct
10 Incorrect 2172 ms 32848 KB Output isn't correct
11 Incorrect 3884 ms 17884 KB Output isn't correct
12 Incorrect 1104 ms 19792 KB Output isn't correct
13 Incorrect 1544 ms 19728 KB Output isn't correct
14 Incorrect 1780 ms 21240 KB Output isn't correct
15 Incorrect 2642 ms 23888 KB Output isn't correct
16 Incorrect 2487 ms 29260 KB Output isn't correct
17 Incorrect 2337 ms 29772 KB Output isn't correct