oj.uz

Submission #704703

# Submission time Handle Problem Language Result Execution time Memory
704703 2023-03-02T16:57:08 Z amin Regions (IOI09_regions) C++14
100 / 100
 5221 ms 55480 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11088 KB Output is correct
2 Correct 6 ms 11088 KB Output is correct
3 Correct 7 ms 11088 KB Output is correct
4 Correct 9 ms 11088 KB Output is correct
5 Correct 9 ms 11180 KB Output is correct
6 Correct 27 ms 11420 KB Output is correct
7 Correct 29 ms 11388 KB Output is correct
8 Correct 39 ms 11496 KB Output is correct
9 Correct 39 ms 12264 KB Output is correct
10 Correct 78 ms 12488 KB Output is correct
11 Correct 90 ms 13140 KB Output is correct
12 Correct 119 ms 14000 KB Output is correct
13 Correct 133 ms 13932 KB Output is correct
14 Correct 211 ms 14836 KB Output is correct
15 Correct 259 ms 19104 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 20432 KB Output is correct
2 Correct 1082 ms 19132 KB Output is correct
3 Correct 1441 ms 25728 KB Output is correct
4 Correct 309 ms 15640 KB Output is correct
5 Correct 288 ms 18544 KB Output is correct
6 Correct 459 ms 18012 KB Output is correct
7 Correct 763 ms 19312 KB Output is correct
8 Correct 1034 ms 29592 KB Output is correct
9 Correct 1793 ms 35896 KB Output is correct
10 Correct 2816 ms 43956 KB Output is correct
11 Correct 2597 ms 39624 KB Output is correct
12 Correct 2769 ms 33492 KB Output is correct
13 Correct 3136 ms 36112 KB Output is correct
14 Correct 3677 ms 37824 KB Output is correct
15 Correct 4599 ms 46468 KB Output is correct
16 Correct 5221 ms 55480 KB Output is correct
17 Correct 3938 ms 53940 KB Output is correct