oj.uz

Submission #856379

# Submission time Handle Problem Language Result Execution time Memory
856379 2023-10-03T09:30:05 Z hqminhuwu Regions (IOI09_regions) C++17
45 / 100
 2806 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 4 ms 22872 KB Output is correct
2 Correct 4 ms 18776 KB Output is correct
3 Correct 4 ms 18776 KB Output is correct
4 Correct 6 ms 18772 KB Output is correct
5 Correct 8 ms 18776 KB Output is correct
6 Correct 13 ms 18776 KB Output is correct
7 Correct 18 ms 18776 KB Output is correct
8 Correct 15 ms 19032 KB Output is correct
9 Correct 26 ms 19288 KB Output is correct
10 Correct 54 ms 19288 KB Output is correct
11 Correct 69 ms 19656 KB Output is correct
12 Correct 89 ms 20056 KB Output is correct
13 Correct 101 ms 19864 KB Output is correct
14 Correct 181 ms 129412 KB Output is correct
15 Correct 242 ms 130128 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1301 ms 130348 KB Output is correct
2 Runtime error 32 ms 131072 KB Execution killed with signal 9
3 Correct 2086 ms 130412 KB Output is correct
4 Correct 169 ms 20540 KB Output is correct
5 Correct 223 ms 22128 KB Output is correct
6 Runtime error 39 ms 43752 KB Execution killed with signal 11
7 Runtime error 42 ms 45904 KB Execution killed with signal 11
8 Runtime error 50 ms 55436 KB Execution killed with signal 11
9 Correct 1532 ms 28056 KB Output is correct
10 Runtime error 79 ms 65840 KB Execution killed with signal 11
11 Correct 2806 ms 27780 KB Output is correct
12 Runtime error 86 ms 58776 KB Execution killed with signal 11
13 Runtime error 79 ms 59132 KB Execution killed with signal 11
14 Runtime error 83 ms 58708 KB Execution killed with signal 11
15 Runtime error 92 ms 67520 KB Execution killed with signal 11
16 Runtime error 92 ms 78076 KB Execution killed with signal 11
17 Runtime error 84 ms 76036 KB Execution killed with signal 11