oj.uz

Submission #566631

# Submission time Handle Problem Language Result Execution time Memory
566631 2022-05-22T13:24:53 Z zaneyu Regions (IOI09_regions) C++14
28 / 100
 1438 ms 131072 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=2;
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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14388 KB Output is correct
2 Correct 14 ms 14416 KB Output is correct
3 Correct 11 ms 14544 KB Output is correct
4 Correct 12 ms 14672 KB Output is correct
5 Correct 14 ms 14800 KB Output is correct
6 Correct 29 ms 17168 KB Output is correct
7 Correct 32 ms 15824 KB Output is correct
8 Correct 42 ms 16464 KB Output is correct
9 Correct 59 ms 23740 KB Output is correct
10 Incorrect 108 ms 19440 KB Output isn't correct
11 Correct 112 ms 18212 KB Output is correct
12 Incorrect 191 ms 28336 KB Output isn't correct
13 Correct 148 ms 18792 KB Output is correct
14 Correct 162 ms 17816 KB Output is correct
15 Correct 201 ms 60900 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 32128 KB Output is correct
2 Correct 769 ms 20232 KB Output is correct
3 Correct 1438 ms 59956 KB Output is correct
4 Runtime error 57 ms 38520 KB Execution killed with signal 11
5 Runtime error 67 ms 40956 KB Execution killed with signal 11
6 Runtime error 68 ms 40600 KB Execution killed with signal 11
7 Runtime error 84 ms 41432 KB Execution killed with signal 11
8 Runtime error 231 ms 131072 KB Execution killed with signal 11
9 Runtime error 176 ms 71756 KB Execution killed with signal 11
10 Runtime error 216 ms 84016 KB Execution killed with signal 11
11 Runtime error 203 ms 47976 KB Execution killed with signal 11
12 Runtime error 197 ms 86344 KB Execution killed with signal 11
13 Runtime error 216 ms 98064 KB Execution killed with signal 11
14 Runtime error 172 ms 51056 KB Execution killed with signal 11
15 Runtime error 222 ms 131072 KB Execution killed with signal 9
16 Runtime error 216 ms 131072 KB Execution killed with signal 9
17 Runtime error 228 ms 113724 KB Execution killed with signal 11