Submission #704702

#	Time	Username	Problem	Language	Result	Execution time	Memory
704702		amin	Regions (IOI09_regions)	C++14	0 / 100	25 ms	12736 KiB

regions

#include <bits/stdc++.h>
#include<cstdio>
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;
    scanf("%d",&n);
    int r,q;
     scanf("%d",&r);
      scanf("%d",&q);

    scanf("%d",&re[0]);
    re[0]--;
    for(int i=1;i<n;i++)
    {
        cout<<i<<endl;
        int x;
         scanf("%d",&x);
         scanf("%d",&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;
     scanf("%d",&x);
      scanf("%d",&y);
    x--;
    y--;
    //cout<<x<<' '<<y<<endl;
    if(ans[{x,y}]!=0)
    {
       printf("%d\n",(ans[{x,y}]+1));
       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;
    printf("%d\n",sum);

}

}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:108: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]
  108 |         if(pl==0||pl==ra[x].size())
      |                   ~~^~~~~~~~~~~~~~
regions.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
regions.cpp:41:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |      scanf("%d",&r);
      |      ~~~~~^~~~~~~~~
regions.cpp:42:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |       scanf("%d",&q);
      |       ~~~~~^~~~~~~~~
regions.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d",&re[0]);
      |     ~~~~~^~~~~~~~~~~~~
regions.cpp:50:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |          scanf("%d",&x);
      |          ~~~~~^~~~~~~~~
regions.cpp:51:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |          scanf("%d",&re[i]);
      |          ~~~~~^~~~~~~~~~~~~
regions.cpp:86:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |      scanf("%d",&x);
      |      ~~~~~^~~~~~~~~
regions.cpp:87:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |       scanf("%d",&y);
      |       ~~~~~^~~~~~~~~

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