oj.uz

Submission #1004602

# Submission time Handle Problem Language Result Execution time Memory
1004602 2024-06-21T10:24:16 Z Mardonbekhazratov Regions (IOI09_regions) C++17
0 / 100
 141 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;

struct SegTree{
    int N;
    vector<int>tree;

    void build(int n){
        N=1;
        while(N<n) N<<=1;

        tree.assign(2*N,0);
    }

    void update(int v,int l,int r,int id,int x){
        cout<<v;
        if(r-l==1){
            tree[v]+=x;
            return;
        }

        int mid=(l+r)/2;

        if(mid>id) update(v<<1,l,mid,id,x);
        else update(v<<1|1,mid,r,id,x);

        tree[v]=tree[v<<1]+tree[v<<1|1];
    }

    void update(int id,int x){
        return update(1,0,N,id,x);
    }

    int get(int v,int l,int r,int ql,int qr){
        if(ql>=r || l>=qr) return 0;
        if(l>=ql && qr>=r) return tree[v];
        
        int mid=(l+r)/2;

        return get(v<<1,l,mid,ql,qr)+get(v<<1|1,mid,r,ql,qr);
    }

    int get(int l,int r){
        return get(1,0,N,l,r);
    }
};

int n,r,q,timer = 0;
vector<int>h,tin,tout;
vector<vector<int>>v,a,dp;
vector<SegTree>S;

void dfs(int x){
    tin[x]=timer++;
    for(int z:v[x]){
        dfs(z);
    }
    tout[x]=timer;
}

int solve(int r1,int r2){
    if(dp[r1][r2]!=-1) return dp[r1][r2];
    int ans=0;
    for(int x:a[r1]){
        ans+=S[r2].get(tin[x],tout[x]);
    }
    return dp[r1][r2]=ans;
}

signed main(){
    cin>>n>>r>>q;
    h.resize(n+1);
    a.resize(r+1);
    S.resize(r+1);
    cin>>h[1];
    v.assign(n+1,vector<int>(0));
    dp.assign(r+1,vector<int>(r+1,-1));
    for(int i=2,x;i<=n;i++){
        cin>>x>>h[i];
        v[x].push_back(i);
    }
    tin.resize(n+1);
    tout.resize(n+1);
    dfs(1);
    for(int i=1;i<=n;i++){
        a[h[i]].push_back(i);
    }
    for(int i=1;i<=r;i++){
        S[i].build(timer);
        for(int x:a[i]){
            S[i].update(tin[x],1);
        }
    }
    while(q--){
        int r1,r2;
        cin>>r1>>r2;
        cout<<solve(r1,r2)<<'\n';
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 596 KB Execution killed with signal 13
2 Runtime error 0 ms 344 KB Execution killed with signal 13
3 Runtime error 0 ms 400 KB Execution killed with signal 13
4 Runtime error 0 ms 344 KB Execution killed with signal 13
5 Runtime error 0 ms 600 KB Execution killed with signal 13
6 Runtime error 2 ms 2648 KB Execution killed with signal 13
7 Runtime error 3 ms 2900 KB Execution killed with signal 13
8 Runtime error 3 ms 3976 KB Execution killed with signal 13
9 Runtime error 12 ms 20568 KB Execution killed with signal 13
10 Runtime error 30 ms 57432 KB Execution killed with signal 13
11 Runtime error 27 ms 37460 KB Execution killed with signal 13
12 Runtime error 79 ms 119888 KB Execution killed with signal 13
13 Runtime error 57 ms 90660 KB Execution killed with signal 13
14 Runtime error 51 ms 54776 KB Execution killed with signal 13
15 Runtime error 90 ms 128840 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 131072 KB Execution killed with signal 9
2 Runtime error 141 ms 131072 KB Execution killed with signal 9
3 Runtime error 95 ms 131072 KB Execution killed with signal 9
4 Runtime error 64 ms 131072 KB Execution killed with signal 9
5 Runtime error 70 ms 131072 KB Execution killed with signal 9
6 Runtime error 56 ms 131072 KB Execution killed with signal 9
7 Runtime error 55 ms 131072 KB Execution killed with signal 9
8 Runtime error 54 ms 131072 KB Execution killed with signal 9
9 Runtime error 55 ms 131072 KB Execution killed with signal 9
10 Runtime error 54 ms 131072 KB Execution killed with signal 9
11 Runtime error 56 ms 131072 KB Execution killed with signal 9
12 Runtime error 56 ms 131072 KB Execution killed with signal 9
13 Runtime error 54 ms 131072 KB Execution killed with signal 9
14 Runtime error 53 ms 131072 KB Execution killed with signal 9
15 Runtime error 55 ms 131072 KB Execution killed with signal 9
16 Runtime error 53 ms 131072 KB Execution killed with signal 9
17 Runtime error 59 ms 131072 KB Execution killed with signal 9