oj.uz

Submission #918882

# Submission time Handle Problem Language Result Execution time Memory
918882 2024-01-30T15:52:52 Z ShaShi Regions (IOI09_regions) C++17
35 / 100
 3630 ms 131072 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, bool bala) {
    if (bala) res[id][arr[v]]++;
    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 6 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 5 ms 19228 KB Output is correct
4 Correct 7 ms 19032 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 13 ms 19032 KB Output is correct
7 Correct 22 ms 19032 KB Output is correct
8 Correct 19 ms 19032 KB Output is correct
9 Correct 30 ms 19544 KB Output is correct
10 Correct 45 ms 19544 KB Output is correct
11 Correct 76 ms 20056 KB Output is correct
12 Correct 93 ms 20568 KB Output is correct
13 Correct 143 ms 20312 KB Output is correct
14 Correct 197 ms 21052 KB Output is correct
15 Correct 191 ms 25668 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1410 ms 50928 KB Output isn't correct
2 Incorrect 1677 ms 43780 KB Output isn't correct
3 Incorrect 2239 ms 42504 KB Output isn't correct
4 Correct 162 ms 21080 KB Output is correct
5 Correct 223 ms 24576 KB Output is correct
6 Incorrect 373 ms 116568 KB Output isn't correct
7 Incorrect 1174 ms 46256 KB Output isn't correct
8 Runtime error 106 ms 131072 KB Execution killed with signal 9
9 Correct 1708 ms 31752 KB Output is correct
10 Incorrect 2793 ms 120504 KB Output isn't correct
11 Correct 3630 ms 32328 KB Output is correct
12 Incorrect 1028 ms 35152 KB Output isn't correct
13 Incorrect 1406 ms 35416 KB Output isn't correct
14 Incorrect 1637 ms 66340 KB Output isn't correct
15 Incorrect 2407 ms 39496 KB Output isn't correct
16 Incorrect 2123 ms 44632 KB Output isn't correct
17 Incorrect 2163 ms 76668 KB Output isn't correct