Submission #1127578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127578		bunhadasou	Regions (IOI09_regions)	C++17	70 / 100	8042 ms	57616 KiB

regions

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define ll long long
#define bit(n,i) ((n>i)&1)
#define sz(x) (int)x.size()
#define TASK "cf"
using namespace std;

struct fenwick{
    vector<int>ft;
    int lim;
    void reset(int _n){
        ft.assign(_n+100,0);
        lim=_n;
    }
    void upd(int pos,int val){
        for (;pos<=lim;pos+=pos&-pos) ft[pos]+=val;
    }
    int get(int pos){
        int res=0;
        if (pos<=0) return res;
        for (;pos>0;pos-=pos&-pos) res+=ft[pos];
        return res;
    }
    int getting(int l,int r){
        if (l>r) return 0;
        return get(r)-get(l-1);
    }
};

const int BLOCK=500;
const int maxn=2e5+5;
int in[maxn],out[maxn];
fenwick ft;
int cnt[maxn],a[maxn],face[maxn];
vector<int>color[maxn];
vector<int>adj[maxn];
int n,r,q;
int num_special,time_dfs;
vector<int>sp;
ll ans_1[410][maxn],ans_2[maxn][410];

void dfs(int u,int p){
    in[u]=++time_dfs;
    for (auto v:adj[u]) if (v!=p) dfs(v,u);
    out[u]=time_dfs;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen(TASK".inp","r",stdin);
    // freopen(TASK".out","w",stdout);
    cin>>n>>r>>q;
    ft.reset(n);
    cin>>a[1];
    cnt[a[1]]++;
    color[a[1]].PB(1);
    for (int i=2;i<=n;i++) {
        int x; cin>>x>>a[i];
        adj[x].PB(i);
        cnt[a[i]]++;
        color[a[i]].PB(i);
    }
    dfs(1,-1);
    for (int i=1;i<=r;i++) {
        if (cnt[i]>=BLOCK) {
            face[i]=++num_special;
            sp.PB(i);
        }
    }

    for (int c=1;c<=r;c++){
        for (auto x:color[c]) ft.upd(in[x],1);
        for (auto cc:sp) {
            for (auto u:color[cc]){
                ans_1[face[cc]][c]+=ft.getting(in[u],out[u]);
            }
        }
        for (auto x:color[c]) ft.upd(in[x],-1);


        for (auto x:color[c]) {
            ft.upd(in[x],1);ft.upd(out[x]+1,-1);
        }

        for (auto cc:sp){
            for (auto u:color[cc]) ans_2[c][face[cc]]+=ft.get(in[u]);
        }
        for (auto x:color[c]) {
            ft.upd(in[x],-1);ft.upd(out[x]+1,1);
        }
    }
//    cout<<ans_2[1][face[3]]<<"\n";
    while(q--){
        int c_1,c_2;cin>>c_1>>c_2;
        if (face[c_1]){
            cout<<ans_1[face[c_1]][c_2]<<"\n";
            cout.flush();
            continue;
        }
        if (face[c_2]){
            cout<<ans_2[c_1][face[c_2]]<<"\n";
            cout.flush();
            continue;
        }
        ll res=0;
        for (auto x:color[c_2]) ft.upd(in[x],1);
        for (auto x:color[c_1]) res+=ft.getting(in[x],out[x]);
        cout<<res<<"\n";
        cout.flush();
        for (auto x:color[c_2]) ft.upd(in[x],-1);
    }


    cerr<<"Time running "<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 55 / 85