oj.uz

Submission #918884

# Submission time Handle Problem Language Result Execution time Memory
918884 2024-01-30T15:58:07 Z ShaShi Regions (IOI09_regions) C++17
100 / 100
 3633 ms 105148 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)2e5 + 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[MAXN], 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, int bala) {
    res[id][arr[v]] += bala; bala += (arr[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 5 ms 19032 KB Output is correct
2 Correct 6 ms 19032 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 6 ms 19228 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 12 ms 19032 KB Output is correct
7 Correct 16 ms 19032 KB Output is correct
8 Correct 19 ms 19032 KB Output is correct
9 Correct 25 ms 19544 KB Output is correct
10 Correct 53 ms 19544 KB Output is correct
11 Correct 83 ms 19544 KB Output is correct
12 Correct 94 ms 20080 KB Output is correct
13 Correct 127 ms 19836 KB Output is correct
14 Correct 218 ms 20312 KB Output is correct
15 Correct 195 ms 22832 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1438 ms 35400 KB Output is correct
2 Correct 1627 ms 32260 KB Output is correct
3 Correct 2193 ms 32968 KB Output is correct
4 Correct 165 ms 20312 KB Output is correct
5 Correct 225 ms 22096 KB Output is correct
6 Correct 352 ms 68660 KB Output is correct
7 Correct 1192 ms 32764 KB Output is correct
8 Correct 774 ms 105148 KB Output is correct
9 Correct 1746 ms 27256 KB Output is correct
10 Correct 2788 ms 75164 KB Output is correct
11 Correct 3633 ms 26904 KB Output is correct
12 Correct 1075 ms 30180 KB Output is correct
13 Correct 1381 ms 30548 KB Output is correct
14 Correct 1614 ms 44648 KB Output is correct
15 Correct 2279 ms 34620 KB Output is correct
16 Correct 2001 ms 39704 KB Output is correct
17 Correct 2015 ms 55184 KB Output is correct