oj.uz

Submission #918883

# Submission time Handle Problem Language Result Execution time Memory
918883 2024-01-30T15:56:46 Z ShaShi Regions (IOI09_regions) C++17
35 / 100
 3615 ms 105140 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) {
    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 4 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 6 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 17 ms 19032 KB Output is correct
8 Correct 20 ms 19032 KB Output is correct
9 Correct 26 ms 19544 KB Output is correct
10 Correct 45 ms 19544 KB Output is correct
11 Correct 70 ms 19544 KB Output is correct
12 Correct 94 ms 20056 KB Output is correct
13 Correct 123 ms 19756 KB Output is correct
14 Correct 212 ms 20568 KB Output is correct
15 Correct 183 ms 22772 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1348 ms 35400 KB Output isn't correct
2 Incorrect 1600 ms 32152 KB Output isn't correct
3 Incorrect 2248 ms 32736 KB Output isn't correct
4 Correct 161 ms 20456 KB Output is correct
5 Correct 243 ms 22104 KB Output is correct
6 Incorrect 430 ms 68704 KB Output isn't correct
7 Incorrect 1119 ms 32856 KB Output isn't correct
8 Incorrect 759 ms 105140 KB Output isn't correct
9 Correct 1673 ms 27232 KB Output is correct
10 Incorrect 2794 ms 75384 KB Output isn't correct
11 Correct 3615 ms 26808 KB Output is correct
12 Incorrect 1024 ms 30336 KB Output isn't correct
13 Incorrect 1442 ms 30452 KB Output isn't correct
14 Incorrect 1616 ms 44652 KB Output isn't correct
15 Incorrect 2298 ms 34620 KB Output isn't correct
16 Incorrect 2041 ms 39796 KB Output isn't correct
17 Incorrect 2133 ms 55112 KB Output isn't correct