oj.uz

Submission #1091312

# Submission time Handle Problem Language Result Execution time Memory
1091312 2024-09-20T13:13:58 Z asli_bg Regions (IOI09_regions) C++11
30 / 100
 8000 ms 105568 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+3;

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];
        }
    }
}

void merge(vi& c,vi& a,vi& b){
    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++]);
    }
}

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);
    merge(t[nd],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 16 ms 28504 KB Output is correct
2 Correct 15 ms 28504 KB Output is correct
3 Correct 20 ms 28504 KB Output is correct
4 Correct 19 ms 28504 KB Output is correct
5 Correct 21 ms 28556 KB Output is correct
6 Correct 26 ms 28760 KB Output is correct
7 Correct 51 ms 29016 KB Output is correct
8 Correct 40 ms 29016 KB Output is correct
9 Correct 86 ms 30508 KB Output is correct
10 Correct 121 ms 31708 KB Output is correct
11 Correct 266 ms 32648 KB Output is correct
12 Correct 395 ms 35216 KB Output is correct
13 Correct 328 ms 35788 KB Output is correct
14 Correct 717 ms 36924 KB Output is correct
15 Correct 1665 ms 44508 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8042 ms 54272 KB Time limit exceeded
2 Execution timed out 8037 ms 54980 KB Time limit exceeded
3 Execution timed out 8058 ms 59336 KB Time limit exceeded
4 Correct 822 ms 36944 KB Output is correct
5 Correct 1196 ms 42576 KB Output is correct
6 Correct 5785 ms 44408 KB Output is correct
7 Execution timed out 8087 ms 52420 KB Time limit exceeded
8 Execution timed out 8090 ms 64192 KB Time limit exceeded
9 Execution timed out 8071 ms 81080 KB Time limit exceeded
10 Execution timed out 8071 ms 91336 KB Time limit exceeded
11 Execution timed out 8077 ms 92344 KB Time limit exceeded
12 Execution timed out 8060 ms 89024 KB Time limit exceeded
13 Execution timed out 8029 ms 90312 KB Time limit exceeded
14 Execution timed out 8021 ms 92188 KB Time limit exceeded
15 Execution timed out 8054 ms 96392 KB Time limit exceeded
16 Execution timed out 8016 ms 105568 KB Time limit exceeded
17 Execution timed out 8074 ms 103872 KB Time limit exceeded