Submission #1103736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103736		salmon	Regions (IOI09_regions)	C++14	55 / 100	2463 ms	131072 KiB

regions

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

#define pb(x) push_back(x)

int N;
int K,Q;
int parent[200100];
vector<int> children[200100];
int lst[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 = 501;
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",&K);
    scanf(" %d",&Q);

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

    kv[lst[1]].push_back(1);

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

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

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

    dfs(1);
//printf("s %d",pre[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] = 0;
        }
    }

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

    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 = 1; i <= K; i++){
        for(int j : prv[i]){
            printf("%d ",j);
        }
        printf("\n");
    }
    for(int i = 1; i <= K; i++){
        for(int j : pov[i]){
            printf("%d ",j);
        }
        printf("\n");
    }*/

    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",ans1[h][in]);
        }
        else{

            int it = 0;
            int it1 = 0;
            long long int V = 0;
            int v = 0;

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

            it = 0;
            it1 = 0;
            v = 0;

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

            printf("%d\n",V);
        }
        fflush(stdout);
    }
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
*/

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:104:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int j = 0; j < f.size(); j++){
      |                            ~~^~~~~~~~~~
regions.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int j = 0; j < f.size(); j++){
      |                    ~~^~~~~~~~~~
regions.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:162:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  162 |             printf("%d\n",ans[in][h1]);
      |                     ~^    ~~~~~~~~~~~
      |                      |              |
      |                      int            long long int
      |                     %lld
regions.cpp:166:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  166 |             printf("%d\n",ans1[h][in]);
      |                     ~^    ~~~~~~~~~~~
      |                      |              |
      |                      int            long long int
      |                     %lld
regions.cpp:175:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |             for(int i = 0; i < prv[h1].size() + prv[h].size() - 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:190:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |             for(int i = 0; i < prv[h1].size() + pov[h].size() - 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:201:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  201 |             printf("%d\n",V);
      |                     ~^    ~
      |                      |    |
      |                      int  long long int
      |                     %lld
regions.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
regions.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
regions.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
regions.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf(" %d",&lst[1]);
      |     ~~~~~^~~~~~~~~~~~~~~
regions.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf(" %d",&parent[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
regions.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
regions.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf(" %d",&h1);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85