oj.uz

Submission #856383

# Submission time Handle Problem Language Result Execution time Memory
856383 2023-10-03T09:33:36 Z hqminhuwu Regions (IOI09_regions) C++17
100 / 100
 2620 ms 87716 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
 
 
using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
 
int fst[N],lst[N],f[N],res[N][500],par[N],cnt[N],n,r,q,cur;
vector <int> a[N],w[N],ww[N];
void go (int u){
    fst[u] = ++cur;
    w[f[u]].pb(cur);
    ww[f[u]].pb(u);
    for (int v : a[u])
        go(v);
    lst[u] = cur;
}
 
int od[N];
void dfs (int u, int sum, int x){
    res[f[u]][od[x]] += sum;;
    sum += (f[u] == x);
    for (int v : a[u])
        dfs(v,sum,x);
}
 
int i,u,v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> r >> q;
    cin >> f[1];
    cnt[f[1]]++;
    forr (i,2,n)
        cin >> par[i],a[par[i]].pb(i),
        cin >> f[i],cnt[f[i]]++;
    forr (i,1,r)
        w[i].pb(0);
    go(1);
    forr (i,1,r)
        w[i].pb(oo);
    int numcmp = 0;
    forr (i,1,r){
        if (cnt[i] <= sqrt(n))
            continue;
        od[i] = ++numcmp;
        dfs(1,0,i);
    }
    while (q--){
        cin >> u >> v;
        if (od[u])
            cout <<res[v][od[u]] << endl;
        else {
            int ans = 0;
            for (int i : ww[u]){
                ans += upper_bound(all(w[v]),lst[i]) - lower_bound(all(w[v]),fst[i]);
            }
                cout << ans << endl;
        }
    }
    return 0;
}
/*
 
 
 
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 4 ms 18776 KB Output is correct
3 Correct 5 ms 18888 KB Output is correct
4 Correct 5 ms 18776 KB Output is correct
5 Correct 7 ms 18776 KB Output is correct
6 Correct 13 ms 18776 KB Output is correct
7 Correct 14 ms 18776 KB Output is correct
8 Correct 17 ms 19032 KB Output is correct
9 Correct 28 ms 19288 KB Output is correct
10 Correct 56 ms 19288 KB Output is correct
11 Correct 81 ms 19544 KB Output is correct
12 Correct 80 ms 20056 KB Output is correct
13 Correct 107 ms 19864 KB Output is correct
14 Correct 163 ms 22360 KB Output is correct
15 Correct 213 ms 24920 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 25356 KB Output is correct
2 Correct 1549 ms 24396 KB Output is correct
3 Correct 2089 ms 27112 KB Output is correct
4 Correct 154 ms 20540 KB Output is correct
5 Correct 238 ms 22060 KB Output is correct
6 Correct 369 ms 36164 KB Output is correct
7 Correct 742 ms 43352 KB Output is correct
8 Correct 799 ms 48024 KB Output is correct
9 Correct 1555 ms 27928 KB Output is correct
10 Correct 2209 ms 82232 KB Output is correct
11 Correct 2620 ms 28016 KB Output is correct
12 Correct 811 ms 62112 KB Output is correct
13 Correct 1249 ms 62372 KB Output is correct
14 Correct 1492 ms 68268 KB Output is correct
15 Correct 2102 ms 82696 KB Output is correct
16 Correct 2121 ms 87716 KB Output is correct
17 Correct 2087 ms 77072 KB Output is correct