oj.uz

Submission #895373

# Submission time Handle Problem Language Result Execution time Memory
895373 2023-12-29T20:03:04 Z Ahmed57 Regions (IOI09_regions) C++17
33 / 100
 1485 ms 54296 KB 
#include <bits/stdc++.h>
 
using namespace std;
long long frq[25001],a3[25001];
int xd[25001],x,p,lol[200001],j,a,b,B = 100;
vector<int> adj[200001];
vector<int> bi;
int rev[25001];
int cs1[25001][101],cs2[25001][101];
int timer = 0;
vector<pair<int,int>> rngs[25001];
int idx,all;
void dfs(int i){
    frq[lol[i]]++;
    a3[lol[i]]++;
    timer++;
    int sav = timer;
    for(j = 0;j<bi.size();j++){
        //cout<<i<<" "<<qu[i][j].first<<" "<<qu[i][j].second<<endl;
        cs1[lol[i]][j]+=frq[bi[j]];
        cs2[lol[i]][j]-=a3[bi[j]];
    }
    for(int w = 0;w<adj[i].size();w++){
        dfs(adj[i][w]);
    }
    for(j = 0;j<bi.size();j++){
        cs2[lol[i]][j]+=a3[bi[j]];
    }
    rngs[lol[i]].push_back({timer,sav});
    frq[lol[i]]--;
}
int bit[200001];
void add(int x,int v){
    while(x<=timer){
        bit[x]+=v;
        x+=(x&-x);
    }
}
int sum(int x){
    int su = 0;
    while(x>=1){
        su+=bit[x];
        x-=(x&-x);
    }
    return su;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,r,q;cin>>n>>r>>q;
    cin>>x;xd[x]++;
    lol[1] = x;
    for(int i = 2;i<=n;i++){
        cin>>p>>x;
        xd[x]++;
        lol[i] = x;
        adj[p].push_back(i);
    }
    for(int i = 1;i<=r;i++){
        if(xd[i]>=B){
            rev[i] = bi.size();
            bi.push_back(i);
        }
    }
    dfs(1);
    for(int i = 1;i<=r;i++){
        sort(rngs[i].begin(),rngs[i].end());
    }
    for(int i = 1;i<=q;i++){
        cin>>a>>b;
        if(xd[b]<B&&xd[a]>=B){
            cout<<cs1[b][rev[a]]<<endl;
        }else if(xd[b]>=B){
            cout<<cs2[a][rev[b]]<<endl;
        }else{
            idx = 0 ;all = 0;
            for(j = 0;j<rngs[a].size();j++){
                while(idx<rngs[b].size()&&rngs[b][idx].first<=rngs[a][j].first){
                    add(rngs[b][idx++].second,1);
                }
                all+=sum(timer)-sum(rngs[a][j].second-1);
            }while(idx>0){
                add(rngs[b][--idx].second,-1);
            }
            cout<<all<<endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(j = 0;j<bi.size();j++){
      |               ~^~~~~~~~~~
regions.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int w = 0;w<adj[i].size();w++){
      |                   ~^~~~~~~~~~~~~~
regions.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(j = 0;j<bi.size();j++){
      |               ~^~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:78:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for(j = 0;j<rngs[a].size();j++){
      |                       ~^~~~~~~~~~~~~~~
regions.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 while(idx<rngs[b].size()&&rngs[b][idx].first<=rngs[a][j].first){
      |                       ~~~^~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 5 ms 8536 KB Output is correct
6 Correct 9 ms 8796 KB Output is correct
7 Correct 15 ms 8536 KB Output is correct
8 Correct 21 ms 8800 KB Output is correct
9 Correct 26 ms 9380 KB Output is correct
10 Correct 49 ms 9140 KB Output is correct
11 Correct 74 ms 9312 KB Output is correct
12 Correct 97 ms 9912 KB Output is correct
13 Correct 118 ms 9528 KB Output is correct
14 Incorrect 75 ms 12020 KB Output isn't correct
15 Incorrect 100 ms 16296 KB Output isn't correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 428 ms 15232 KB Output isn't correct
2 Incorrect 458 ms 13756 KB Output isn't correct
3 Incorrect 722 ms 17804 KB Output isn't correct
4 Correct 129 ms 16480 KB Output is correct
5 Correct 235 ms 18936 KB Output is correct
6 Correct 322 ms 17536 KB Output is correct
7 Correct 443 ms 22892 KB Output is correct
8 Incorrect 589 ms 30268 KB Output isn't correct
9 Incorrect 1012 ms 32396 KB Output isn't correct
10 Incorrect 1158 ms 43896 KB Output isn't correct
11 Incorrect 1485 ms 34764 KB Output isn't correct
12 Incorrect 817 ms 32216 KB Output isn't correct
13 Incorrect 951 ms 33304 KB Output isn't correct
14 Incorrect 1079 ms 36060 KB Output isn't correct
15 Incorrect 1312 ms 43496 KB Output isn't correct
16 Incorrect 1281 ms 54296 KB Output isn't correct
17 Incorrect 1308 ms 52232 KB Output isn't correct