Submission #1126308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126308		alecurse	Regions (IOI09_regions)	C++20	75 / 100	8055 ms	110088 KiB

regions

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <unordered_map>
#define ll long long int
using namespace std;
ll N, R, Q;
vector<ll> regions;
vector<vector<ll> > adj;
vector<unordered_map<ll,ll> > sets;
vector<unordered_map<ll,ll> > res;
vector<bool> toprecompute;
vector<vector<ll> > regionsnodes;
vector<vector<ll> > regionsnodesapp;
vector<ll> fapp, lapp;
ll currentindex=0;
void dfs(ll x) {
    fapp[x]=currentindex;
    currentindex++;
    for(auto b : adj[x]) {
        dfs(b);
        if(sets[b].size()>sets[x].size()) {
            swap(sets[b],sets[x]);
        }
        for(auto el : sets[b]) {
            sets[x][el.first]+=el.second;
        }
    }
    lapp[x]=currentindex;
    currentindex++;
    if(toprecompute[regions[x]]) {
        for(auto el : sets[x]) {
            res[regions[x]][el.first]+=el.second;
        }
    }
    sets[x][regions[x]]++;
}

ll findres(ll first, ll last, vector<ll> &v) {
    ll a = 0, b=v.size()-1;
    ll maxindex=v.size();
    while(a<=b) {
        ll k = (a+b)/2;
        if(v[k]>first) {
            maxindex=min(maxindex,k);
            b=k-1;
        } else {
            a=k+1;
        }
    }
    ll minindex=-1;
    a=0,b=v.size()-1;
    while(a<=b) {
        ll k = (a+b)/2;
        if(v[k]<last) {
            minindex=max(minindex,k);
            a=k+1;
        } else {
            b=k-1;
        }
    }
    return max((ll)0,minindex-maxindex+1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    cin>>N>>R>>Q;
    regions.resize(N);
    adj.resize(N);
    fapp.resize(N);
    lapp.resize(N);
    sets.resize(N);
    toprecompute.resize(R);
    res.resize(R);
    regionsnodes.resize(R);
    regionsnodesapp.resize(R);
    cin>>regions[0];
    regions[0]--;
    ll root = 400;
    regionsnodes[regions[0]].push_back(0);
    for(ll i=1;i<N;i++) {
        ll p;
        cin>>p;
        p--;
        adj[p].push_back(i);
        cin>>regions[i];
        regions[i]--;
        regionsnodes[regions[i]].push_back(i);
    }
    for(ll i=0;i<R;i++) {
        if(regionsnodes[i].size()>root) {
            toprecompute[i]=true;
        }
    }

    dfs(0);
    for(ll i=0;i<R;i++) {
        for(auto el : regionsnodes[i]) {
            regionsnodesapp[i].push_back(fapp[el]);
        }
    }
    for(ll i=0;i<R;i++) {
        sort(regionsnodesapp[i].begin(),regionsnodesapp[i].end());
    }
    for(ll i=0;i<Q;i++) {
        ll r1, r2;
        cin>>r1>>r2;
        r1--;
        r2--;
        if(regionsnodes[r1].size()>root) {
            cout<<res[r1][r2]<<"\n";
            cout.flush();
            continue;
        }   
        ll tres=0;
        for(auto el : regionsnodes[r1]) {
            tres+=findres(fapp[el],lapp[el],regionsnodesapp[r2]);
        }
        cout<<tres<<"\n";
        cout.flush();
    }
    // for(ll i=0;i<Q;i++) {
    //     cout<<ans[i]<<"\n";
    // }
}

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