oj.uz

Submission #856376

# Submission time Handle Problem Language Result Execution time Memory
856376 2023-10-03T09:25:15 Z hqminhuwu Regions (IOI09_regions) C++17
50 / 100
 2706 ms 131072 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[500][N],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]]++;
    go(1);
    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 22872 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 5 ms 18776 KB Output is correct
5 Correct 7 ms 19028 KB Output is correct
6 Correct 13 ms 18876 KB Output is correct
7 Correct 18 ms 18776 KB Output is correct
8 Correct 19 ms 19032 KB Output is correct
9 Correct 27 ms 19288 KB Output is correct
10 Correct 47 ms 19288 KB Output is correct
11 Correct 69 ms 19544 KB Output is correct
12 Correct 88 ms 19956 KB Output is correct
13 Correct 100 ms 19736 KB Output is correct
14 Correct 176 ms 129360 KB Output is correct
15 Correct 220 ms 130136 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 130356 KB Output is correct
2 Correct 1545 ms 131072 KB Output is correct
3 Correct 2086 ms 131032 KB Output is correct
4 Correct 160 ms 20456 KB Output is correct
5 Correct 230 ms 21848 KB Output is correct
6 Runtime error 37 ms 43400 KB Execution killed with signal 11
7 Runtime error 43 ms 45648 KB Execution killed with signal 11
8 Runtime error 50 ms 55188 KB Execution killed with signal 11
9 Correct 1550 ms 27884 KB Output is correct
10 Runtime error 84 ms 65788 KB Execution killed with signal 11
11 Correct 2706 ms 27520 KB Output is correct
12 Runtime error 84 ms 58276 KB Execution killed with signal 11
13 Runtime error 77 ms 58596 KB Execution killed with signal 11
14 Runtime error 92 ms 58376 KB Execution killed with signal 11
15 Runtime error 89 ms 67008 KB Execution killed with signal 11
16 Runtime error 84 ms 77772 KB Execution killed with signal 11
17 Runtime error 86 ms 75508 KB Execution killed with signal 11