oj.uz

Submission #704699

# Submission time Handle Problem Language Result Execution time Memory
704699 2023-03-02T16:33:40 Z amin Regions (IOI09_regions) C++14
1 / 100
 5801 ms 55056 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;
    }

    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:102: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]
  102 |         if(pl==0||pl==ra[x].size())
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11088 KB Output is correct
2 Incorrect 5 ms 11088 KB Output isn't correct
3 Incorrect 6 ms 11088 KB Output isn't correct
4 Incorrect 7 ms 11088 KB Output isn't correct
5 Incorrect 7 ms 11216 KB Output isn't correct
6 Incorrect 11 ms 11332 KB Output isn't correct
7 Incorrect 11 ms 11416 KB Output isn't correct
8 Incorrect 20 ms 11516 KB Output isn't correct
9 Incorrect 22 ms 12176 KB Output isn't correct
10 Incorrect 33 ms 12476 KB Output isn't correct
11 Runtime error 39 ms 13036 KB Execution killed with signal 13
12 Runtime error 42 ms 14000 KB Execution killed with signal 13
13 Runtime error 71 ms 13912 KB Execution killed with signal 13
14 Runtime error 124 ms 14716 KB Execution killed with signal 13
15 Runtime error 138 ms 18976 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 19748 KB Time limit exceeded (wall clock)
2 Execution timed out 4305 ms 18424 KB Time limit exceeded (wall clock)
3 Execution timed out 4094 ms 23596 KB Time limit exceeded (wall clock)
4 Incorrect 190 ms 15680 KB Output isn't correct
5 Runtime error 121 ms 18580 KB Execution killed with signal 13
6 Runtime error 498 ms 17784 KB Execution killed with signal 13
7 Execution timed out 258 ms 18620 KB Time limit exceeded (wall clock)
8 Execution timed out 450 ms 29384 KB Time limit exceeded (wall clock)
9 Runtime error 837 ms 35564 KB Execution killed with signal 13
10 Runtime error 1831 ms 43652 KB Execution killed with signal 13
11 Runtime error 2025 ms 39272 KB Execution killed with signal 13
12 Runtime error 2359 ms 33300 KB Execution killed with signal 13
13 Runtime error 2722 ms 36008 KB Execution killed with signal 13
14 Runtime error 3164 ms 37192 KB Execution killed with signal 13
15 Runtime error 3828 ms 46272 KB Execution killed with signal 13
16 Runtime error 3895 ms 55056 KB Execution killed with signal 13
17 Execution timed out 5801 ms 53452 KB Time limit exceeded (wall clock)