oj.uz

Submission #704702

# Submission time Handle Problem Language Result Execution time Memory
704702 2023-03-02T16:51:10 Z amin Regions (IOI09_regions) C++14
0 / 100
 25 ms 12736 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 11088 KB Execution killed with signal 13
2 Incorrect 5 ms 11088 KB Output isn't correct
3 Execution timed out 5 ms 11088 KB Time limit exceeded (wall clock)
4 Execution timed out 5 ms 11088 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 11088 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 11216 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 11344 KB Time limit exceeded (wall clock)
8 Runtime error 12 ms 11520 KB Execution killed with signal 13
9 Runtime error 13 ms 12120 KB Execution killed with signal 13
10 Runtime error 16 ms 12276 KB Execution killed with signal 13
11 Runtime error 25 ms 12736 KB Execution killed with signal 13
12 Execution timed out 12 ms 11512 KB Time limit exceeded (wall clock)
13 Execution timed out 14 ms 11344 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 11472 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 11600 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12 ms 11600 KB Time limit exceeded (wall clock)
2 Execution timed out 14 ms 11472 KB Time limit exceeded (wall clock)
3 Execution timed out 12 ms 11600 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 11472 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 11508 KB Time limit exceeded (wall clock)
6 Execution timed out 13 ms 11420 KB Time limit exceeded (wall clock)
7 Execution timed out 12 ms 11472 KB Time limit exceeded (wall clock)
8 Execution timed out 14 ms 11600 KB Time limit exceeded (wall clock)
9 Execution timed out 13 ms 11524 KB Time limit exceeded (wall clock)
10 Execution timed out 13 ms 11600 KB Time limit exceeded (wall clock)
11 Execution timed out 12 ms 11344 KB Time limit exceeded (wall clock)
12 Execution timed out 14 ms 11600 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 11484 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 11448 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 11560 KB Time limit exceeded (wall clock)
16 Execution timed out 14 ms 11596 KB Time limit exceeded (wall clock)
17 Execution timed out 13 ms 11600 KB Time limit exceeded (wall clock)