oj.uz

Submission #898943

# Submission time Handle Problem Language Result Execution time Memory
898943 2024-01-05T09:30:57 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
100 / 100
 3437 ms 128312 KB 
// In the name of the God 
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
 
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5, maxr = 25e3+5, sq = 200, sq_ = 1e3+5;
 
int n, q, t = 0, cur = 0, re[maxn], id[maxr], cnt[sq_], res[sq_][maxr], in[maxn], out[maxn];
vector <int> adj[maxn], oc[maxr], amir[maxr];

void dfs(int v = 0) {
    in[v] = t++; amir[re[v]].pb(in[v]);
    if (oc[re[v]].size() >= sq) cnt[id[re[v]]]++;
    for (int i = 0; i < sq_; i++) res[i][re[v]] += cnt[i];
    for (int u : adj[v]) dfs(u);
    if (oc[re[v]].size() >= sq) cnt[id[re[v]]]--;
    out[v] = t;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> q;
    cin >> re[0]; re[0]--;
    oc[re[0]].pb(0);
    for (int i = 1; i < n; i++) {
        int p; cin >> p >> re[i]; re[i]--;
        adj[--p].pb(i);
        oc[re[i]].pb(i);
    }
    for (int i = 0; i < maxr; i++) {
        if (oc[i].size() >= sq) id[i] = cur++;
    }
    dfs();
    for (int i = 0; i < maxr; i++) sort(all(amir[i]));
    while (q--) {
        int r1, r2; cin >> r1 >> r2; r1--, r2--;
        if (oc[r1].size() >= sq) cout << res[id[r1]][r2];
        else {
            int ans = 0;
            for (int v : oc[r1]) {
                int l = lower_bound(all(amir[r2]), in[v])-amir[r2].begin();
                int r = upper_bound(all(amir[r2]), out[v]-1)-amir[r2].begin();
                ans += r-l;
            }
            cout << ans;
        }
        cout << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 105304 KB Output is correct
2 Correct 12 ms 105304 KB Output is correct
3 Correct 12 ms 105304 KB Output is correct
4 Correct 14 ms 105236 KB Output is correct
5 Correct 15 ms 105304 KB Output is correct
6 Correct 20 ms 105304 KB Output is correct
7 Correct 25 ms 105404 KB Output is correct
8 Correct 29 ms 105304 KB Output is correct
9 Correct 43 ms 105816 KB Output is correct
10 Correct 62 ms 105808 KB Output is correct
11 Correct 94 ms 105816 KB Output is correct
12 Correct 119 ms 106468 KB Output is correct
13 Correct 158 ms 106104 KB Output is correct
14 Correct 233 ms 106476 KB Output is correct
15 Correct 245 ms 109648 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 109836 KB Output is correct
2 Correct 576 ms 108208 KB Output is correct
3 Correct 756 ms 111492 KB Output is correct
4 Correct 261 ms 106736 KB Output is correct
5 Correct 378 ms 108816 KB Output is correct
6 Correct 482 ms 108024 KB Output is correct
7 Correct 1103 ms 109212 KB Output is correct
8 Correct 1065 ms 114728 KB Output is correct
9 Correct 2203 ms 114412 KB Output is correct
10 Correct 2322 ms 120868 KB Output is correct
11 Correct 2339 ms 114120 KB Output is correct
12 Correct 1730 ms 115368 KB Output is correct
13 Correct 1996 ms 115780 KB Output is correct
14 Correct 2479 ms 115444 KB Output is correct
15 Correct 3437 ms 120996 KB Output is correct
16 Correct 2209 ms 128312 KB Output is correct
17 Correct 3019 ms 126536 KB Output is correct