Submission #1103751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1103751	2024-10-21T15:42:04 Z	salmon	Regions (IOI09_regions)	C++14	55 / 100	2540 ms	131072 KB

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 = 2001;
int ans[200100/B + 100][25100];
int ans1[25100][200100/B + 100];
vector<int> f;
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

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: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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	23632 KB	Output is correct
2	Correct	5 ms	23632 KB	Output is correct
3	Correct	6 ms	23632 KB	Output is correct
4	Correct	9 ms	23800 KB	Output is correct
5	Correct	10 ms	23632 KB	Output is correct
6	Correct	15 ms	23632 KB	Output is correct
7	Correct	26 ms	23632 KB	Output is correct
8	Correct	29 ms	23632 KB	Output is correct
9	Correct	52 ms	24400 KB	Output is correct
10	Correct	68 ms	24144 KB	Output is correct
11	Correct	111 ms	24400 KB	Output is correct
12	Correct	125 ms	25048 KB	Output is correct
13	Correct	138 ms	24656 KB	Output is correct
14	Correct	192 ms	25168 KB	Output is correct
15	Correct	207 ms	29568 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1111 ms	131072 KB	Execution killed with signal 9
2	Runtime error	302 ms	131072 KB	Execution killed with signal 9
3	Runtime error	307 ms	131072 KB	Execution killed with signal 9
4	Correct	235 ms	25424 KB	Output is correct
5	Correct	332 ms	28240 KB	Output is correct
6	Correct	711 ms	26920 KB	Output is correct
7	Correct	986 ms	27984 KB	Output is correct
8	Correct	896 ms	35972 KB	Output is correct
9	Correct	1429 ms	34604 KB	Output is correct
10	Correct	2052 ms	42896 KB	Output is correct
11	Correct	2540 ms	33608 KB	Output is correct
12	Runtime error	354 ms	131072 KB	Execution killed with signal 9
13	Runtime error	342 ms	131072 KB	Execution killed with signal 9
14	Runtime error	352 ms	131072 KB	Execution killed with signal 9
15	Runtime error	333 ms	131072 KB	Execution killed with signal 9
16	Runtime error	298 ms	131072 KB	Execution killed with signal 9
17	Runtime error	293 ms	131072 KB	Execution killed with signal 9