oj.uz

Submission #856381

# Submission time Handle Problem Language Result Execution time Memory
856381 2023-10-03T09:31:30 Z hqminhuwu Regions (IOI09_regions) C++14
45 / 100
 2728 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]]++;
    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 5 ms 22872 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 5 ms 18776 KB Output is correct
4 Correct 7 ms 18776 KB Output is correct
5 Correct 8 ms 18776 KB Output is correct
6 Correct 12 ms 18776 KB Output is correct
7 Correct 18 ms 18776 KB Output is correct
8 Correct 26 ms 19032 KB Output is correct
9 Correct 33 ms 19540 KB Output is correct
10 Correct 49 ms 19424 KB Output is correct
11 Correct 65 ms 19544 KB Output is correct
12 Correct 84 ms 20136 KB Output is correct
13 Correct 107 ms 19868 KB Output is correct
14 Correct 186 ms 129432 KB Output is correct
15 Correct 215 ms 129984 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1328 ms 130360 KB Output is correct
2 Runtime error 34 ms 131072 KB Execution killed with signal 9
3 Correct 2097 ms 130416 KB Output is correct
4 Correct 144 ms 20568 KB Output is correct
5 Correct 237 ms 21972 KB Output is correct
6 Runtime error 37 ms 43860 KB Execution killed with signal 11
7 Runtime error 65 ms 45916 KB Execution killed with signal 11
8 Runtime error 51 ms 55408 KB Execution killed with signal 11
9 Correct 1547 ms 27932 KB Output is correct
10 Runtime error 86 ms 65944 KB Execution killed with signal 11
11 Correct 2728 ms 27784 KB Output is correct
12 Runtime error 82 ms 58780 KB Execution killed with signal 11
13 Runtime error 77 ms 59172 KB Execution killed with signal 11
14 Runtime error 90 ms 58868 KB Execution killed with signal 11
15 Runtime error 82 ms 67428 KB Execution killed with signal 11
16 Runtime error 84 ms 77904 KB Execution killed with signal 11
17 Runtime error 89 ms 76016 KB Execution killed with signal 11