oj.uz

Submission #856378

# Submission time Handle Problem Language Result Execution time Memory
856378 2023-10-03T09:27:28 Z hqminhuwu Regions (IOI09_regions) C++17
44 / 100
 2648 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 = 3e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
 
int fst[N],lst[N],f[N],res[600][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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31252 KB Output is correct
2 Correct 5 ms 26968 KB Output is correct
3 Correct 6 ms 26968 KB Output is correct
4 Correct 7 ms 26968 KB Output is correct
5 Correct 8 ms 26968 KB Output is correct
6 Correct 13 ms 27224 KB Output is correct
7 Correct 17 ms 26968 KB Output is correct
8 Correct 20 ms 27224 KB Output is correct
9 Correct 25 ms 27480 KB Output is correct
10 Correct 47 ms 27484 KB Output is correct
11 Correct 72 ms 27872 KB Output is correct
12 Correct 82 ms 28248 KB Output is correct
13 Correct 102 ms 27832 KB Output is correct
14 Runtime error 25 ms 131072 KB Execution killed with signal 9
15 Correct 203 ms 130396 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1272 ms 130508 KB Output is correct
2 Runtime error 37 ms 131072 KB Execution killed with signal 9
3 Correct 2033 ms 130584 KB Output is correct
4 Correct 149 ms 28624 KB Output is correct
5 Correct 208 ms 30028 KB Output is correct
6 Runtime error 45 ms 54920 KB Execution killed with signal 11
7 Runtime error 55 ms 56104 KB Execution killed with signal 11
8 Runtime error 61 ms 60584 KB Execution killed with signal 11
9 Correct 1462 ms 35648 KB Output is correct
10 Runtime error 71 ms 65748 KB Execution killed with signal 11
11 Correct 2648 ms 35484 KB Output is correct
12 Runtime error 103 ms 62112 KB Execution killed with signal 11
13 Runtime error 82 ms 62252 KB Execution killed with signal 11
14 Runtime error 87 ms 61892 KB Execution killed with signal 11
15 Runtime error 85 ms 66348 KB Execution killed with signal 11
16 Runtime error 85 ms 71656 KB Execution killed with signal 11
17 Runtime error 78 ms 70376 KB Execution killed with signal 11