oj.uz

Submission #895381

# Submission time Handle Problem Language Result Execution time Memory
895381 2023-12-29T20:14:48 Z Ahmed57 Regions (IOI09_regions) C++17
100 / 100
 3241 ms 121336 KB 
#include <bits/stdc++.h>
 
using namespace std;
long long frq[25001],a3[25001];
int xd[25001],x,p,lol[200001],j,a,b;
const int B = 900;
const int L = (200000+B-1)/B;
vector<int> adj[200001];
vector<int> bi;
int rev[25001];
long long cs1[25001][L],cs2[25001][L];
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:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(j = 0;j<bi.size();j++){
      |               ~^~~~~~~~~~
regions.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int w = 0;w<adj[i].size();w++){
      |                   ~^~~~~~~~~~~~~~
regions.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(j = 0;j<bi.size();j++){
      |               ~^~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:80: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]
   80 |             for(j = 0;j<rngs[a].size();j++){
      |                       ~^~~~~~~~~~~~~~~
regions.cpp:81: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]
   81 |                 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 2 ms 8536 KB Output is correct
2 Correct 1 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 11 ms 8776 KB Output is correct
7 Correct 15 ms 8536 KB Output is correct
8 Correct 21 ms 8792 KB Output is correct
9 Correct 28 ms 9388 KB Output is correct
10 Correct 51 ms 9124 KB Output is correct
11 Correct 78 ms 9420 KB Output is correct
12 Correct 81 ms 9988 KB Output is correct
13 Correct 126 ms 9516 KB Output is correct
14 Correct 196 ms 10060 KB Output is correct
15 Correct 238 ms 14396 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 17448 KB Output is correct
2 Correct 862 ms 15608 KB Output is correct
3 Correct 1640 ms 19868 KB Output is correct
4 Correct 195 ms 10124 KB Output is correct
5 Correct 253 ms 12868 KB Output is correct
6 Correct 866 ms 11172 KB Output is correct
7 Correct 1297 ms 11968 KB Output is correct
8 Correct 1255 ms 19484 KB Output is correct
9 Correct 1937 ms 17176 KB Output is correct
10 Correct 3142 ms 25064 KB Output is correct
11 Correct 3241 ms 15544 KB Output is correct
12 Correct 877 ms 76904 KB Output is correct
13 Correct 1275 ms 77676 KB Output is correct
14 Correct 1404 ms 89016 KB Output is correct
15 Correct 2159 ms 110312 KB Output is correct
16 Correct 2139 ms 121336 KB Output is correct
17 Correct 2081 ms 104988 KB Output is correct