Submission #520202

#	Time	Username	Problem	Language	Result	Execution time	Memory
520202		wildturtle	Regions (IOI09_regions)	C++14	100 / 100	5794 ms	86680 KiB

regions

#include<bits/stdc++.h>
#define ll int
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,n,ans1,T,q,le,ri,l,r,t,rr,p;
ll fix[200005],mp[200005],in[200005],out[200005],mdzime[200005],reg[200005],regsz[200005];
map <ll,ll> ans[200005];
vector <ll> v[200005],v1,vreg[200005];
vector < pair <ll,ll> > vv;
multiset < pair <ll,ll> > ms[200005];
multiset < pair <ll,ll> >::iterator it;
void dfs(ll x,ll y) {
    if(mdzime[reg[x]]) mp[reg[x]]++;
    for(ll i=0;i<v1.size();i++) {
        ans[v1[i]][reg[x]]+=mp[v1[i]];
    }
    for(ll i=0;i<v[x].size();i++) {
        if(v[x][i]==y) continue;
        dfs(v[x][i],x);
    }
    if(mdzime[reg[x]]) mp[reg[x]]--;
}
void dfs1(ll x,ll y) {
    T++;
    in[x]=T;
    vv.pb({in[x],reg[x]});
    for(ll i=0;i<v[x].size();i++) {
        if(v[x][i]==y) continue;
        dfs1(v[x][i],x);
    }
    out[x]=T;
}
int main() {
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>r>>t;
    for(ll i=1;i<=n;i++) {
        if(i!=1) {
            cin>>p;
            v[i].pb(p); 
            v[p].pb(i);
        }
        cin>>reg[i];
        regsz[reg[i]]++;
        vreg[reg[i]].pb(i);
    }
    for(ll i=1;i<=r;i++) {
        if(regsz[i]>=500) {
            mdzime[i]=1;
            v1.pb(i);
        }
    }
    dfs(1,0);
    dfs1(1,0);
    sort(vv.begin(),vv.end());
    for(ll i=0;i<vv.size();i++) {
        //cout<<vv[i].f<<" "<<vv[i].sc<<endl;
        
        fix[vv[i].sc]++;
        ms[vv[i].sc].insert({vv[i].f,fix[vv[i].sc]});
    }
    //cout<<endl;
    while(t--) {
        cin>>a>>b;
        if(vreg[a].size()<500) {
            for(ll i=0;i<vreg[a].size();i++) {
                le=in[vreg[a][i]]; ri=out[vreg[a][i]];
                //cout<<vreg[a][i]<<" "<<le<<" "<<ri<<endl;
                it=ms[b].lower_bound({le,0});
                if(it==ms[b].end()) continue;
                l=(*it).sc;
                it=ms[b].lower_bound({ri,1e9});
                if(it==ms[b].end()) rr=ms[b].size();
                else rr=(*it).sc-1;    
                //cout<<l<<"_"<<rr<<endl;
                ans1+=rr-l+1;
            }
            cout<<ans1<<endl;
            ans1=0;
        } else cout<<ans[a][b]<<endl; 
    }
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(ll i=0;i<v1.size();i++) {
      |                ~^~~~~~~~~~
regions.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(ll i=0;i<v[x].size();i++) {
      |                ~^~~~~~~~~~~~
regions.cpp: In function 'void dfs1(int, int)':
regions.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(ll i=0;i<v[x].size();i++) {
      |                ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(ll i=0;i<vv.size();i++) {
      |                ~^~~~~~~~~~
regions.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(ll i=0;i<vreg[a].size();i++) {
      |                        ~^~~~~~~~~~~~~~~

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