oj.uz

Submission #566632

# Submission time Handle Problem Language Result Execution time Memory
566632 2022-05-22T13:25:04 Z zaneyu Regions (IOI09_regions) C++14
100 / 100
 2682 ms 129564 KB 
/*input
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
vector<int> v[maxn];
vector<int> vv[maxn],v2[maxn];
int bs;
int arr[maxn];
ll save[25000][405];
ll save2[405][25000];
int big[maxn];
int cntt[maxn];
void dfs(int u,vector<int> &cnt){
    if(big[arr[u]]!=-1) cnt[big[arr[u]]]++,cntt[big[arr[u]]]++;
    for(int x:v[u]){
        vector<int> asd(bs);
        dfs(x,asd);
        REP(j,bs) cnt[j]+=asd[j];
    }
    REP(j,bs) save[arr[u]][j]+=cnt[j];
    REP(j,bs) save2[j][arr[u]]+=cntt[j];
    if(big[arr[u]]!=-1) cntt[big[arr[u]]]--;
}
int in[maxn],out[maxn];
int cur=0;
void dfs2(int u){
    in[u]=cur++;
    for(int x:v[u]) dfs2(x);
    out[u]=cur-1;
}
const int blk=500;
int lol[maxn];
int main(){
    int n,r,q;
    cin>>n>>r>>q;
    REP(i,n){
        int p,x;
        if(i) cin>>p,--p,v[p].pb(i);
        cin>>x;
        --x;
        arr[i]=x;
        lol[x]++;
    }
    bs=0;
    REP(i,r){
        if(lol[i]>=blk){
            big[i]=bs++;
        }
        else big[i]=-1;
    }    
    vector<int> cnt(bs);
    dfs(0,cnt);
    dfs2(0);
    REP(i,n) vv[arr[i]].pb(in[i]),v2[arr[i]].pb(out[i]);
    REP(i,r) sort(ALL(vv[i])),sort(ALL(v2[i]));
    while(q--){
        int a,b;
        cin>>a>>b;
        --a,--b;
        if(big[a]!=-1){
            cout<<save2[big[a]][b]<<endl;
            continue;
        }
        if(big[b]!=-1){
            cout<<save[a][big[b]]<<endl;
            continue;
        }
        int l=0,r=0;
        int ans=0;
        for(int x:v2[a]){
            while(r<sz(vv[b]) and vv[b][r]<=x) ++r;
            ans+=r;
        }
        for(int x:vv[a]){
            while(l<sz(vv[b]) and vv[b][l]<x) ++l;
            ans-=l;
        }
        cout<<ans<<endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14416 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 11 ms 14416 KB Output is correct
4 Correct 13 ms 14416 KB Output is correct
5 Correct 13 ms 14416 KB Output is correct
6 Correct 26 ms 14544 KB Output is correct
7 Correct 21 ms 14412 KB Output is correct
8 Correct 42 ms 14544 KB Output is correct
9 Correct 34 ms 15184 KB Output is correct
10 Correct 98 ms 14948 KB Output is correct
11 Correct 132 ms 15188 KB Output is correct
12 Correct 144 ms 15972 KB Output is correct
13 Correct 160 ms 15372 KB Output is correct
14 Correct 249 ms 15944 KB Output is correct
15 Correct 191 ms 21048 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 20716 KB Output is correct
2 Correct 1037 ms 18728 KB Output is correct
3 Correct 1097 ms 24608 KB Output is correct
4 Correct 213 ms 16168 KB Output is correct
5 Correct 363 ms 19264 KB Output is correct
6 Correct 660 ms 39020 KB Output is correct
7 Correct 992 ms 18756 KB Output is correct
8 Correct 871 ms 60448 KB Output is correct
9 Correct 1519 ms 25124 KB Output is correct
10 Correct 2025 ms 34424 KB Output is correct
11 Correct 2682 ms 24032 KB Output is correct
12 Correct 985 ms 71624 KB Output is correct
13 Correct 1339 ms 72900 KB Output is correct
14 Correct 1565 ms 85920 KB Output is correct
15 Correct 1843 ms 113668 KB Output is correct
16 Correct 1948 ms 129564 KB Output is correct
17 Correct 1777 ms 120240 KB Output is correct