oj.uz

Submission #898945

# Submission time Handle Problem Language Result Execution time Memory
898945 2024-01-05T09:34:02 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
100 / 100
 3928 ms 95160 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 = 300, sq_ = 667+2;
 
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 13 ms 72280 KB Output is correct
2 Correct 8 ms 72280 KB Output is correct
3 Correct 9 ms 72532 KB Output is correct
4 Correct 10 ms 72344 KB Output is correct
5 Correct 11 ms 72280 KB Output is correct
6 Correct 15 ms 72368 KB Output is correct
7 Correct 24 ms 72536 KB Output is correct
8 Correct 24 ms 72536 KB Output is correct
9 Correct 31 ms 73048 KB Output is correct
10 Correct 53 ms 72908 KB Output is correct
11 Correct 85 ms 73216 KB Output is correct
12 Correct 108 ms 73560 KB Output is correct
13 Correct 135 ms 73136 KB Output is correct
14 Correct 220 ms 73836 KB Output is correct
15 Correct 221 ms 77000 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 76776 KB Output is correct
2 Correct 1620 ms 75380 KB Output is correct
3 Correct 2237 ms 78764 KB Output is correct
4 Correct 197 ms 74112 KB Output is correct
5 Correct 272 ms 75984 KB Output is correct
6 Correct 412 ms 75160 KB Output is correct
7 Correct 929 ms 76112 KB Output is correct
8 Correct 873 ms 82168 KB Output is correct
9 Correct 1994 ms 81496 KB Output is correct
10 Correct 2579 ms 87916 KB Output is correct
11 Correct 3928 ms 81232 KB Output is correct
12 Correct 1534 ms 82296 KB Output is correct
13 Correct 2020 ms 82732 KB Output is correct
14 Correct 2064 ms 82748 KB Output is correct
15 Correct 2983 ms 87992 KB Output is correct
16 Correct 2833 ms 95160 KB Output is correct
17 Correct 2783 ms 93692 KB Output is correct