oj.uz

Submission #1091302

# Submission time Handle Problem Language Result Execution time Memory
1091302 2024-09-20T12:59:01 Z asli_bg Regions (IOI09_regions) C++11
30 / 100
 8000 ms 105692 KB 
#pragma GCC optimize ("O3,unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef priority_queue<int> pq;
 
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
 
#define carp(x,y,mod) (((x)%mod)*((y)%mod))%mod
#define topla(x,y,mod) (((x)%mod)+((y)%mod))%mod
 
#define mid (l+r)/2
//#define endl '\n'
 
const int MAXN=2e5+5;
const int MAXK=30;

int n,q,r;
vi adj[MAXN];
vi euler;
int sub[MAXN],ind[MAXN],dep[MAXN];
int p[MAXN];
vi t[4*MAXN];
vi reg[MAXN];
int home[MAXN];

void dfs(int nd,int ata,int h){
    dep[nd]=h;
    sub[nd]=1;
    euler.pb(nd);
    for(auto kom:adj[nd]){
        if(kom!=ata){
            dfs(kom,nd,h+1);
            sub[nd]+=sub[kom];
        }
    }
}

vi merge(vi& a,vi& b){
    vi c;
    int sz1=a.size();
    int sz2=b.size();
    int p1,p2;
    p1=p2=0;
    while(p1<sz1 or p2<sz2){
        if(p2>=sz2 or (p1<sz1 and a[p1]<=b[p2])){
            c.pb(a[p1++]);
        }
        else c.pb(b[p2++]);
    }
    return c;
}

void build(int nd=1,int l=1,int r=n){
    if(l==r){
        t[nd].pb(home[euler[l]]);
        return;
    }
    build(nd*2,l,mid);
    build(nd*2+1,mid+1,r);
    t[nd]=merge(t[nd*2],t[nd*2+1]);
}

int query(int ql,int qr,int vv,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return 0;
    if(ql<=l and r<=qr){
        auto bir=lower_bound(all(t[nd]),vv);
        auto iki=upper_bound(all(t[nd]),vv);
        return iki-bir;
    }
    auto s1=query(ql,qr,vv,nd*2,l,mid);
    auto s2=query(ql,qr,vv,nd*2+1,mid+1,r);
    return s1+s2;
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    euler.pb(0);
    cin>>n>>r>>q;
    cin>>home[1];
    reg[home[1]].pb(1);
    FORE(i,2,n+1){
        cin>>p[i]>>home[i];
        reg[home[i]].pb(i);
        adj[p[i]].pb(i);
        adj[i].pb(p[i]);
    }

    dfs(1,0,0);
    FORE(i,1,n+1){
        ind[euler[i]]=i;
    }
    build();

    while(q--){
        int a,b;
        cin>>a>>b;
        int cev=0;
        for(auto el:reg[a]){
            cev+=query(ind[el],ind[el]+sub[el]-1,b);
        }
        cout<<cev<<endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28504 KB Output is correct
2 Correct 17 ms 28504 KB Output is correct
3 Correct 17 ms 28504 KB Output is correct
4 Correct 17 ms 28504 KB Output is correct
5 Correct 20 ms 28760 KB Output is correct
6 Correct 25 ms 28924 KB Output is correct
7 Correct 40 ms 29016 KB Output is correct
8 Correct 51 ms 29132 KB Output is correct
9 Correct 78 ms 30504 KB Output is correct
10 Correct 117 ms 31576 KB Output is correct
11 Correct 268 ms 32644 KB Output is correct
12 Correct 403 ms 35204 KB Output is correct
13 Correct 294 ms 35800 KB Output is correct
14 Correct 711 ms 36920 KB Output is correct
15 Correct 1624 ms 44488 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8066 ms 54216 KB Time limit exceeded
2 Execution timed out 8042 ms 54980 KB Time limit exceeded
3 Execution timed out 8032 ms 59416 KB Time limit exceeded
4 Correct 800 ms 36952 KB Output is correct
5 Correct 1184 ms 42564 KB Output is correct
6 Correct 5597 ms 44412 KB Output is correct
7 Execution timed out 8006 ms 52236 KB Time limit exceeded
8 Execution timed out 8037 ms 64196 KB Time limit exceeded
9 Execution timed out 8016 ms 81084 KB Time limit exceeded
10 Execution timed out 8064 ms 91328 KB Time limit exceeded
11 Execution timed out 8019 ms 92348 KB Time limit exceeded
12 Execution timed out 8054 ms 89024 KB Time limit exceeded
13 Execution timed out 8054 ms 90312 KB Time limit exceeded
14 Execution timed out 8042 ms 91996 KB Time limit exceeded
15 Execution timed out 8098 ms 96444 KB Time limit exceeded
16 Execution timed out 8058 ms 105692 KB Time limit exceeded
17 Execution timed out 8069 ms 103872 KB Time limit exceeded