Submission #1103720

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1103720	2024-10-21T15:02:27 Z	salmon	Regions (IOI09_regions)	C++14	Compilation error	0 ms	0 KB

regions

#include <bits/stdc++.h>
using namespace std;

#define pb(x) push_back(x)

int N;
int R,Q;
int parent[200100];
vector<int> children[200100];
int lst[200100];
int k[200100];
vector<int> kv[200100];
vector<int> pov[200100];
vector<int> prv[200100];
int pre[200100];
int invpre[200100];
int post[200100];
int cont = 0;
const int B = 500;
long long int ans[200100/B + 100][25100];
long long int ans1[25100][200100/B + 100];
vector<int> f;
long long int fk[25100][200100/B + 100];
map<int,int> mep;
int h1,h;

void dfs(int i){
    pre[i] = cont;
    invpre[cont] = i;
    cont++;

    for(int j  : children[i]){
        dfs(j);
    }

    post[i] = cont - 1;
}

void fil(int i){
    for(pair<int,int> ii : mep){
        ans[ii.first][lst[i]] += ii.second;
    }

    if(kv[lst[i]].size() >= B){
        mep[lst[i]]++;
    }

    for(int j : children[i]){
        fil(j);
    }

    if(kv[lst[i]].size() >= B){
        mep[lst[i]]--;
    }
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&R);
    scanf(" %d",&Q);

    parent[1] = -1;
    scanf(" %d",&lst[1]);

    for(int i = 1; i <= K; i++){
        k[i] = 0;
    }

    for(int i = 2; i <= N; i++){
        scanf(" %d",&parent[i]);
        scanf(" %d",&lst[i]);
        k[lst[i]]++;

        children[parent[i]].pb(i);

        kv[lst[i]].push_back(i);
    }

    dfs(1);

    for(int i = 1; i <= K; i++){
        if(!kv[i].empty()){
            for(int j : kv[i]){
                pov[i].push_back(post[j]);
                prv[i].push_back(pre[j]);
            }
            sort(pov[i].begin(),pov[i].end());
            sort(prv[i].begin(),prv[i].end());

            pov[i].push_back(N + 5);
            prv[i].push_back(N + 5);
        }

        if(kv[i].size() >= B){
            f.push_back(i);
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < f.size(); j++){
            fk[i][j] = 0;
        }
    }

    for(int i = 0; i < N; i++){
        if(i != 0){
            for(int j = 0; j < f.size(); j++){
                fk[i][j] = fk[i - 1][j];
            }
        }

        if(kv[invpre[i]].size() >= B){
            int h = invpre[i];

            int in = lower_bound(f.begin(),f.end(),h) - f.begin();

            fk[i][in]++;
        }
    }

    for(int i = 1; i <= K; i++){
        for(int j = 0; j < f.size(); j++){
            ans1[i][j]
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < f.size(); j++){
            int in = invpre[i];

            ans1[lst[in]][j] += fk[post[in]][j] - fk[pre[in]][j];
        }
    }

    fil(1);

    for(int i = 0; i < Q; i++){
        scanf(" %d",&h);
        scanf(" %d",&h1);

        if(kv[h].size() == 0 || kv[h1].size() == 0){
            printf("0\n");
        }
        else if(kv[h].size() >= B){
            int in = lower_bound(f.begin(),f.end(),h) - f.begin();
            printf("%d\n",ans[in][h1]);
        }
        else if(kv[h1].size() >= B){
            int in = lower_bound(f.begin(),f.end(),h1) - f.begin();
            printf("%d\n",ans[h][in]);
        }
        else{
            int it = 0;
            int it1 = 0;
            long long int V = 0;
            int v = 0;

            for(int i = 0; i < pov[h1].size() + pov[h].size() - 2; i++){
                if(pov[h][it] <= pov[h1][it1]){
                    v++;
                    it++;
                }
                else{
                    V -= v;
                    it1++;
                }
            }

            for(int i = 0; i < prv[h1].size() + pov[h].size() - 2; i++){
                if(pov[h][it] <= prv[h1][it1]){
                    v++;
                    it++;
                }
                else{
                    V -= v;
                    it1++;
                }
            }

            printf("%d\n",ans);
        }
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:66:25: error: 'K' was not declared in this scope
   66 |     for(int i = 1; i <= K; i++){
      |                         ^
regions.cpp:82:25: error: 'K' was not declared in this scope
   82 |     for(int i = 1; i <= K; i++){
      |                         ^
regions.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:108:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for(int j = 0; j < f.size(); j++){
      |                            ~~^~~~~~~~~~
regions.cpp:122:25: error: 'K' was not declared in this scope
  122 |     for(int i = 1; i <= K; i++){
      |                         ^
regions.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:124:23: error: expected ';' before '}' token
  124 |             ans1[i][j]
      |                       ^
      |                       ;
  125 |         }
      |         ~              
regions.cpp:124:22: warning: statement has no effect [-Wunused-value]
  124 |             ans1[i][j]
      |             ~~~~~~~~~^
regions.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:147:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  147 |             printf("%d\n",ans[in][h1]);
      |                     ~^    ~~~~~~~~~~~
      |                      |              |
      |                      int            long long int
      |                     %lld
regions.cpp:151:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  151 |             printf("%d\n",ans[h][in]);
      |                     ~^    ~~~~~~~~~~
      |                      |             |
      |                      int           long long int
      |                     %lld
regions.cpp:159:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int i = 0; i < pov[h1].size() + pov[h].size() - 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:170:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |             for(int i = 0; i < prv[h1].size() + pov[h].size() - 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:181:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int (*)[25100]' [-Wformat=]
  181 |             printf("%d\n",ans);
      |                     ~^    ~~~
      |                      |    |
      |                      int  long long int (*)[25100]
regions.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
regions.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf(" %d",&R);
      |     ~~~~~^~~~~~~~~~
regions.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
regions.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf(" %d",&lst[1]);
      |     ~~~~~^~~~~~~~~~~~~~~
regions.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf(" %d",&parent[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
regions.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
regions.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         scanf(" %d",&h1);
      |         ~~~~~^~~~~~~~~~~