oj.uz

Submission #895380

# Submission time Handle Problem Language Result Execution time Memory
895380 2023-12-29T20:13:20 Z Ahmed57 Regions (IOI09_regions) C++17
90 / 100
 3443 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;
const int B = 700;
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 1 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 8 ms 8784 KB Output is correct
7 Correct 13 ms 8536 KB Output is correct
8 Correct 22 ms 8800 KB Output is correct
9 Correct 28 ms 9388 KB Output is correct
10 Correct 46 ms 9132 KB Output is correct
11 Correct 80 ms 9352 KB Output is correct
12 Correct 93 ms 9816 KB Output is correct
13 Correct 126 ms 9516 KB Output is correct
14 Correct 215 ms 10068 KB Output is correct
15 Correct 238 ms 14396 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 17448 KB Output is correct
2 Correct 877 ms 15616 KB Output is correct
3 Correct 1681 ms 19844 KB Output is correct
4 Correct 207 ms 10148 KB Output is correct
5 Correct 243 ms 12888 KB Output is correct
6 Correct 869 ms 11352 KB Output is correct
7 Correct 1288 ms 12196 KB Output is correct
8 Correct 1275 ms 19640 KB Output is correct
9 Correct 1970 ms 17264 KB Output is correct
10 Correct 3184 ms 24640 KB Output is correct
11 Correct 3443 ms 15560 KB Output is correct
12 Correct 845 ms 93260 KB Output is correct
13 Correct 1237 ms 94188 KB Output is correct
14 Correct 1467 ms 109588 KB Output is correct
15 Runtime error 53 ms 131072 KB Execution killed with signal 9
16 Runtime error 56 ms 131072 KB Execution killed with signal 9
17 Correct 2159 ms 125744 KB Output is correct