oj.uz

답안 #1103746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103746 2024-10-21T15:38:56 Z salmon Regions (IOI09_regions) C++14
0 / 100
 107 ms 41544 KB 
#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 = 1001;
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);
        }
    }
return 0;
    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: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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 23888 KB Unexpected end of file - int32 expected
2 Incorrect 5 ms 23888 KB Unexpected end of file - int32 expected
3 Incorrect 5 ms 23888 KB Unexpected end of file - int32 expected
4 Incorrect 5 ms 23888 KB Unexpected end of file - int32 expected
5 Incorrect 6 ms 23888 KB Unexpected end of file - int32 expected
6 Incorrect 5 ms 23888 KB Unexpected end of file - int32 expected
7 Incorrect 5 ms 23888 KB Unexpected end of file - int32 expected
8 Incorrect 8 ms 23888 KB Unexpected end of file - int32 expected
9 Incorrect 6 ms 24400 KB Unexpected end of file - int32 expected
10 Incorrect 8 ms 24400 KB Unexpected end of file - int32 expected
11 Incorrect 10 ms 24824 KB Unexpected end of file - int32 expected
12 Incorrect 11 ms 25180 KB Unexpected end of file - int32 expected
13 Incorrect 11 ms 24924 KB Unexpected end of file - int32 expected
14 Incorrect 13 ms 25680 KB Unexpected end of file - int32 expected
15 Incorrect 21 ms 27472 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 28240 KB Unexpected end of file - int32 expected
2 Incorrect 39 ms 27456 KB Unexpected end of file - int32 expected
3 Incorrect 30 ms 29776 KB Unexpected end of file - int32 expected
4 Incorrect 14 ms 25680 KB Unexpected end of file - int32 expected
5 Incorrect 15 ms 26960 KB Unexpected end of file - int32 expected
6 Incorrect 21 ms 26960 KB Unexpected end of file - int32 expected
7 Incorrect 27 ms 27976 KB Unexpected end of file - int32 expected
8 Incorrect 34 ms 32080 KB Unexpected end of file - int32 expected
9 Incorrect 61 ms 33352 KB Unexpected end of file - int32 expected
10 Incorrect 59 ms 37448 KB Unexpected end of file - int32 expected
11 Incorrect 80 ms 33356 KB Unexpected end of file - int32 expected
12 Incorrect 90 ms 34516 KB Unexpected end of file - int32 expected
13 Incorrect 92 ms 34488 KB Unexpected end of file - int32 expected
14 Incorrect 107 ms 34720 KB Unexpected end of file - int32 expected
15 Incorrect 74 ms 38128 KB Unexpected end of file - int32 expected
16 Incorrect 71 ms 41544 KB Unexpected end of file - int32 expected
17 Incorrect 82 ms 38644 KB Unexpected end of file - int32 expected