Submission #704703

#	Time	Username	Problem	Language	Result	Execution time	Memory
704703		amin	Regions (IOI09_regions)	C++14	100 / 100	5221 ms	55480 KiB

regions

#include <bits/stdc++.h>

using namespace std;
 #define ll long long

 vector<int>v[200001],p[200001];
 vector<pair<int,int> >ma[30000];
 vector<pair<int,int> >ra[30000];

 int re[200001];

 vector<int>df;


 void dfs(int in)
 {
     int l=df.size();
     df.push_back(in);
p[re[in]].push_back(df.size()-1);
     for(auto i:v[in])
     {
         dfs(i);
     }
     int r=df.size();
     df.push_back(in);
     ma[re[in]].push_back({l,1});
     ma[re[in]].push_back({r+1,-1});


 }

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.flush();
    int n;
    cin>>n;
    int r,q;
    cin>>r>>q;

    cin>>re[0];
    re[0]--;
    for(int i=1;i<n;i++)
    {
        int x;
        cin>>x;
        cin>>re[i];
        re[i]--;

        x--;
        v[x].push_back(i);
    }
    dfs(0);
for(int i=0;i<r;i++)
{

    sort(ma[i].begin(),ma[i].end());
    int u=0;
    //cout<<i<<endl;
int h=ma[i].size();
    for(int y=0;y<h;y++)
    {
       // cout<<y<<' ';
       // cout<<ma[i].size()<<endl;
        u+=ma[i][y].second;
        if(y==(h-1))
        {
            ra[i].push_back({ma[i][y].first,0});
            break;
        }
        if(ma[i][y].first==ma[i][y+1].first)
            continue;
        ra[i].push_back({ma[i][y].first,u});
    //    cout<<ma[i][y].first<<' '<<u<<endl;
    }

}
map<pair<int,int>,int >ans;
while(q--)
{
    int x,y;
    cin>>x>>y;
    x--;
    y--;
    if(ans[{x,y}]!=0)
    {
        cout<<ans[{x,y}]+1<<endl;
        continue;
    }

    int h=p[y].size();
   // cout<<ra[x].size()<<' ';
    int sum=0;
   // cout<<h<<endl;
    for(int i=0;i<h;i++)
    {
        pair<int,int>z=make_pair(p[y][i],1000000000);
        //cout<<p[y][i]<<' ';
       int pl=upper_bound(ra[x].begin(),ra[x].end(),z)-ra[x].begin();
//cout<<pl<<endl;
        if(pl==0||pl==ra[x].size())
        {

            continue;
        }
     pl--;
     sum+=(ra[x][pl].second);

    }
    ans[{x,y}]=sum-1;
    cout<<sum<<endl;
}

}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         if(pl==0||pl==ra[x].size())
      |                   ~~^~~~~~~~~~~~~~

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