Submission #1127633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127633		bunhadasou	Regions (IOI09_regions)	C++17	80 / 100	8076 ms	37564 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 all(x) x.begin(),x.end()
#define TASK "cf"
using namespace std;

const int BLOCK=750;
const int maxn=2e5+5;
int in[maxn],out[maxn],face[maxn],cur_color[maxn],a[maxn];
ll ans_1[405][maxn],ans_2[maxn][405];
vector<int>adj[maxn],color[maxn];
int n,r,q;
int time_dfs,num_special;
vector<int>sp;
vector<pair<int,int>>node[maxn];


void dfs(int u){
//    cout<<u<<" ";
    in[u]=++time_dfs;
    for (auto v:adj[u]) dfs(v);
    out[u]=time_dfs;
}

void dfs2(int u){
    cur_color[a[u]]++;
    for (auto v:adj[u]) dfs2(v);
    cur_color[a[u]]--;
    for (auto x:sp) {
        ans_1[face[x]][a[u]]+=cur_color[x];
//        ans_2[a[u]][face[x]]+=cur_color[a[u]];
    }
}

ll solve(int a,int b,vector<pair<int,int>>c){
    int lo=0,hi=sz(c)-1;
    int res_1=-1,res_2=-1;
    while(hi-lo>=0){
        int mid=(hi+lo)>>1;
        if (c[mid].fi<=b) {
            res_2=mid;
            lo=mid+1;
        }
        else hi=mid-1;
    }
    lo=0,hi=sz(c)-1;
    while(hi-lo>=0){
        int mid=(hi+lo)>>1;
        if (c[mid].fi>=a){
            res_1=mid;
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if (res_1==-1) return 0;
    if (res_2==-1) return 0;
    return res_2-res_1+1;
}

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;
    cin>>a[1];
    color[a[1]].PB(1);
    for (int i=2;i<=n;i++) {
        int x; cin>>x>>a[i];
        adj[x].PB(i);
        color[a[i]].PB(i);
    }
    for (int i=1;i<=r;i++) {
        if (sz(color[i])>=BLOCK) {
            face[i]=++num_special;
            sp.PB(i);
        }
    }
    dfs(1);
    dfs2(1);
//    cout<<sz(sp)<<"\n";
    for (int i=1;i<=n;i++) node[a[i]].PB(mp(in[i],i));

    for (int i=1;i<=r;i++) sort(all(node[i]));

    while(q--){
        int c_1,c_2;cin>>c_1>>c_2;
        if (sz(color[c_1])>=BLOCK) {
//            cout<<"b ";
            cout<<ans_1[face[c_1]][c_2]<<"\n";cout.flush();

            continue;
        }
//        if (sz(color[c_2])>=BLOCK){
//            cout<<"c ";
//            cout<<ans_2[c_1][face[c_2]]<<"\n";cout.flush();
//            continue;
//        }
//        cout<<"a";
        ll res=0;
        for (auto x:node[c_1]) res+=solve(in[x.se],out[x.se],node[c_2]);
        cout<<res<<"\n";
        cout.flush();
    }


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

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