Submission #1069820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069820		doducanh	Regions (IOI09_regions)	C++14	100 / 100	3456 ms	30800 KiB

regions

#include <bits/stdc++.h>

using namespace std;
const int maxn=2e5+7;
int a[maxn];
vector<int>adj[maxn];
int innode[2*maxn];
int n,r,q;
vector<int>comp[25005];
vector<vector<int>>ans;
int in[maxn];
int out[maxn];
int cnt;
void dfs(int u,int par)
{
    in[u]=++cnt;
    comp[a[u]].push_back(in[u]);
    innode[in[u]]=u;
    for(int v:adj[u])if(v!=par){
        dfs(v,u);
    }
    out[u]=++cnt;
}
void dfs1(int u,int curr,int tmp)
{
    if(a[u]==curr)tmp++;
    ans[curr][a[u]]+=tmp;
    for(int v:adj[u]){
        dfs1(v,curr,tmp);
    }
}
int main()
{
    cin>>n>>r>>q;
    cin>>a[1];
    for(int i=2;i<=n;i++){
        int x,k;
        cin>>x>>k;
        adj[x].push_back(i);
        a[i]=k;
    }
    ans.resize(r+1);
    dfs(1,0);
    int sz=sqrt(n);
    for(int i=1;i<=r;i++){
        if(comp[i].size()>=sz){
            ans[i]=vector<int>(r+1);
            dfs1(1,i,0);
        }
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        if(comp[x].size()>=sz){
            cout<<ans[x][y]<<"\n";
        }
        else{
            int res=0;
            for(int x:comp[x]){
                res+=lower_bound(comp[y].begin(),comp[y].end(),out[innode[x]])-lower_bound(comp[y].begin(),comp[y].end(),in[innode[x]]);
            }
            cout<<res<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:46:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(comp[i].size()>=sz){
      |            ~~~~~~~~~~~~~~^~~~
regions.cpp:54:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         if(comp[x].size()>=sz){
      |            ~~~~~~~~~~~~~~^~~~

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