oj.uz

Submission #895379

# Submission time Handle Problem Language Result Execution time Memory
895379 2023-12-29T20:09:36 Z Ahmed57 Regions (IOI09_regions) C++17
70 / 100
 3261 ms 131072 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 = 500;
vector<int> adj[200001];
vector<int> bi;
int rev[25001];
long long cs1[25001][501],cs2[25001][501];
int timer = 0;
vector<pair<int,int>> rngs[25001];
long long 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: 'long long 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 5 ms 8616 KB Output is correct
6 Correct 10 ms 8788 KB Output is correct
7 Correct 17 ms 8536 KB Output is correct
8 Correct 16 ms 8804 KB Output is correct
9 Correct 28 ms 9372 KB Output is correct
10 Correct 45 ms 9132 KB Output is correct
11 Correct 95 ms 9304 KB Output is correct
12 Correct 89 ms 9816 KB Output is correct
13 Correct 130 ms 9528 KB Output is correct
14 Correct 197 ms 10072 KB Output is correct
15 Correct 247 ms 14400 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 15380 KB Output is correct
2 Correct 954 ms 15616 KB Output is correct
3 Correct 1702 ms 19868 KB Output is correct
4 Correct 234 ms 10140 KB Output is correct
5 Correct 256 ms 12988 KB Output is correct
6 Correct 565 ms 66580 KB Output is correct
7 Correct 1288 ms 12044 KB Output is correct
8 Correct 1239 ms 99408 KB Output is correct
9 Correct 1926 ms 17224 KB Output is correct
10 Correct 3168 ms 24772 KB Output is correct
11 Correct 3261 ms 15560 KB Output is correct
12 Runtime error 64 ms 131072 KB Execution killed with signal 9
13 Runtime error 48 ms 131072 KB Execution killed with signal 9
14 Runtime error 48 ms 131072 KB Execution killed with signal 9
15 Runtime error 53 ms 131072 KB Execution killed with signal 9
16 Runtime error 62 ms 131072 KB Execution killed with signal 9
17 Runtime error 54 ms 131072 KB Execution killed with signal 9