Submission #895334

#	Time	Username	Problem	Language	Result	Execution time	Memory
895334		Ahmed57	Regions (IOI09_regions)	C++17	0 / 100	46 ms	22408 KiB

regions

#include <bits/stdc++.h>
 
using namespace std;
int frq[25001],a3[25001],xd[25001],ans[25001],x,p,lol[200001],j,a,b,B = 500;
map<pair<int,int>,int> mp;
vector<int> adj[200001];
vector<pair<int,int>> lo,qu[25001];
set<int> qu2[200001];
void dfs(int i){
    frq[lol[i]]++;
    a3[lol[i]]++;
    for(j = 0;j<qu[lol[i]].size();j++){
        //cout<<i<<" "<<qu[i][j].first<<" "<<qu[i][j].second<<endl;
        ans[qu[lol[i]][j].second] += frq[qu[lol[i]][j].first];
    }
    for(auto e:qu2[lol[i]]){
        mp[{lol[i],e}] -=a3[e];
    }
    for(int w = 0;w<adj[i].size();w++){
        dfs(adj[i][w]);
    }
    for(auto e:qu2[lol[i]]){
        mp[{lol[i],e}] +=a3[e];
    }
    frq[lol[i]]--;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,r,q;cin>>n>>r>>q;
    cin>>x;xd[x]++;
    lol[1] = x;
    for(int i = 2;i<=n;i++){
        cin>>p>>x;
        xd[x]++;
        lol[i] = x;
        adj[p].push_back(i);
    }
    for(int i = 1;i<=q;i++){
        cin>>a>>b;
        if(xd[b]<B){
            qu[b].push_back({a,i});
            ans[i] = 0;
        }else{
            lo.push_back({a,b});
            qu2[a].insert(b);
            ans[i] = -1;
        }
    }
    dfs(1);
    for(int i = 1;i<=q;i++){
        if(ans[i]==-1){
            ans[i] = mp[{lo[i-1].first,lo[i-1].second}];
        }cout<<ans[i]<<"\n";
    }
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(j = 0;j<qu[lol[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~~
regions.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int w = 0;w<adj[i].size();w++){
      |                   ~^~~~~~~~~~~~~~

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