oj.uz

답안 #1103725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103725 2024-10-21T15:10:57 Z salmon Regions (IOI09_regions) C++14
0 / 100
 2141 ms 131072 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];
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",&K);
    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] = 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 = 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 < 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",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: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: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:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int j = 0; j < f.size(); j++){
      |                    ~~^~~~~~~~~~
regions.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int j = 0; j < f.size(); j++){
      |                        ~~^~~~~~~~~~
regions.cpp:153:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  153 |             printf("%d\n",ans[in][h1]);
      |                     ~^    ~~~~~~~~~~~
      |                      |              |
      |                      int            long long int
      |                     %lld
regions.cpp:157:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  157 |             printf("%d\n",ans1[h][in]);
      |                     ~^    ~~~~~~~~~~~
      |                      |              |
      |                      int            long long int
      |                     %lld
regions.cpp:166:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |             for(int i = 0; i < pov[h1].size() + pov[h].size() - 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:177:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             for(int i = 0; i < prv[h1].size() + pov[h].size() - 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:188:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  188 |             printf("%d\n",V);
      |                     ~^    ~
      |                      |    |
      |                      int  long long int
      |                     %lld
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",&K);
      |     ~~~~~^~~~~~~~~~
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:145:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
regions.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         scanf(" %d",&h1);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 24912 KB Output isn't correct
2 Incorrect 4 ms 24912 KB Output isn't correct
3 Incorrect 6 ms 24912 KB Output isn't correct
4 Incorrect 7 ms 24912 KB Output isn't correct
5 Incorrect 10 ms 24912 KB Output isn't correct
6 Incorrect 17 ms 25168 KB Output isn't correct
7 Incorrect 25 ms 24912 KB Output isn't correct
8 Incorrect 31 ms 25168 KB Output isn't correct
9 Incorrect 47 ms 25680 KB Output isn't correct
10 Incorrect 72 ms 25704 KB Output isn't correct
11 Incorrect 90 ms 25680 KB Output isn't correct
12 Incorrect 119 ms 21072 KB Output isn't correct
13 Incorrect 139 ms 25936 KB Output isn't correct
14 Incorrect 165 ms 26508 KB Output isn't correct
15 Incorrect 157 ms 25680 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 131072 KB Execution killed with signal 9
2 Runtime error 45 ms 131072 KB Execution killed with signal 9
3 Runtime error 53 ms 131072 KB Execution killed with signal 9
4 Incorrect 228 ms 26896 KB Output isn't correct
5 Incorrect 322 ms 29620 KB Output isn't correct
6 Runtime error 35 ms 131072 KB Execution killed with signal 9
7 Incorrect 866 ms 29264 KB Output isn't correct
8 Runtime error 59 ms 131072 KB Execution killed with signal 9
9 Incorrect 1304 ms 35352 KB Output isn't correct
10 Incorrect 1754 ms 43804 KB Output isn't correct
11 Incorrect 2141 ms 34408 KB Output isn't correct
12 Runtime error 79 ms 131072 KB Execution killed with signal 9
13 Runtime error 77 ms 131072 KB Execution killed with signal 9
14 Runtime error 125 ms 131072 KB Execution killed with signal 9
15 Runtime error 103 ms 131072 KB Execution killed with signal 9
16 Runtime error 89 ms 131072 KB Execution killed with signal 9
17 Runtime error 85 ms 131072 KB Execution killed with signal 9