oj.uz

Submission #918877

# Submission time Handle Problem Language Result Execution time Memory
918877 2024-01-30T15:40:26 Z ShaShi Regions (IOI09_regions) C++17
35 / 100
 3683 ms 110856 KB 
#include <bits/stdc++.h>
// #define int long long 
#define F first
#define S second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pb push_back
// #define endl "\n"
 
 
using namespace std;
typedef long long ll;
 
const int MAXN = (int)3e5 + 7;
const int MOD = 999999893;
const int INF = (int)1e9 + 7;
const int SQ = 450;

 
int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, ans2;
int arr[MAXN], num[MAXN], id[SQ], st[MAXN], ft[MAXN];
int res[SQ][MAXN];
vector<int> adj[MAXN], col[MAXN], vec[MAXN];


void DFSsz(int v) {
    st[v] = flag; vec[arr[v]].pb(flag++);

    for (int u:adj[v]) DFSsz(u);

    ft[v] = flag;
}


void DFS(int v, int x, int id, bool bala) {
    if (bala) res[id][arr[v]]++;
    bala |= (v == x);

    for (int u:adj[v]) DFS(u, x, id, bala);
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

    cin >> n >> m >> q;

    cin >> arr[1];
    col[arr[1]].pb(1); num[arr[1]]++;


    for (int i=2; i<=n; i++) {
        cin >> u >> arr[i];

        adj[u].pb(i); col[arr[i]].pb(i); num[arr[i]]++;
    }


    DFSsz(1); flag = 0;

    for (int i=1; i<=m; i++) {
        if (num[i] >= SQ) {
            id[i] = flag;
            DFS(1, i, flag, 0); flag++;
        }
    }

    for (int i=1; i<=m; i++) vec[i].pb(INF);

    while (q--) {
        cin >> u >> v;

        // cout << "!";

        if (num[u] < SQ) {
            ans = 0;

            for (int w:col[u]) ans += lower_bound(all(vec[v]), ft[w])-lower_bound(all(vec[v]), st[w]);
      
            cout << ans << endl;
        } else {
            cout << res[id[u]][v] << endl;
        }
    }


    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29272 KB Output is correct
2 Correct 7 ms 29272 KB Output is correct
3 Correct 9 ms 29272 KB Output is correct
4 Correct 9 ms 29272 KB Output is correct
5 Correct 12 ms 29272 KB Output is correct
6 Correct 20 ms 29272 KB Output is correct
7 Correct 21 ms 29272 KB Output is correct
8 Correct 21 ms 29272 KB Output is correct
9 Correct 29 ms 29784 KB Output is correct
10 Correct 55 ms 29784 KB Output is correct
11 Correct 88 ms 29784 KB Output is correct
12 Correct 99 ms 30344 KB Output is correct
13 Correct 121 ms 30040 KB Output is correct
14 Correct 212 ms 30384 KB Output is correct
15 Correct 186 ms 32816 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1425 ms 49516 KB Output isn't correct
2 Incorrect 1677 ms 42172 KB Output isn't correct
3 Incorrect 2180 ms 45072 KB Output isn't correct
4 Correct 166 ms 30672 KB Output is correct
5 Correct 225 ms 32168 KB Output is correct
6 Incorrect 354 ms 87092 KB Output isn't correct
7 Incorrect 1166 ms 46852 KB Output isn't correct
8 Incorrect 729 ms 110856 KB Output isn't correct
9 Correct 1698 ms 37000 KB Output is correct
10 Incorrect 2771 ms 103528 KB Output isn't correct
11 Correct 3683 ms 36376 KB Output is correct
12 Incorrect 1018 ms 37848 KB Output isn't correct
13 Incorrect 1394 ms 38252 KB Output isn't correct
14 Incorrect 1577 ms 60352 KB Output isn't correct
15 Incorrect 2310 ms 42308 KB Output isn't correct
16 Incorrect 2146 ms 47192 KB Output isn't correct
17 Incorrect 2190 ms 71024 KB Output isn't correct