oj.uz

답안 #1103723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103723 2024-10-21T15:09:28 Z salmon Regions (IOI09_regions) C++14
0 / 100
 2153 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",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",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",ans[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 5 ms 24912 KB Output isn't correct
2 Incorrect 5 ms 24912 KB Output isn't correct
3 Incorrect 6 ms 24912 KB Output isn't correct
4 Incorrect 9 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 22 ms 24912 KB Output isn't correct
8 Incorrect 29 ms 25168 KB Output isn't correct
9 Incorrect 38 ms 25680 KB Output isn't correct
10 Incorrect 65 ms 25424 KB Output isn't correct
11 Incorrect 82 ms 25936 KB Output isn't correct
12 Incorrect 106 ms 26624 KB Output isn't correct
13 Incorrect 132 ms 26016 KB Output isn't correct
14 Incorrect 156 ms 26716 KB Output isn't correct
15 Incorrect 156 ms 31056 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 38 ms 131072 KB Execution killed with signal 9
2 Runtime error 40 ms 131072 KB Execution killed with signal 9
3 Runtime error 40 ms 131072 KB Execution killed with signal 9
4 Incorrect 227 ms 26704 KB Output isn't correct
5 Incorrect 310 ms 29520 KB Output isn't correct
6 Runtime error 45 ms 131072 KB Execution killed with signal 9
7 Incorrect 875 ms 29264 KB Output isn't correct
8 Runtime error 50 ms 131072 KB Execution killed with signal 9
9 Incorrect 1421 ms 35532 KB Output isn't correct
10 Incorrect 1686 ms 43592 KB Output isn't correct
11 Incorrect 2153 ms 34376 KB Output isn't correct
12 Runtime error 94 ms 131072 KB Execution killed with signal 9
13 Runtime error 84 ms 131072 KB Execution killed with signal 9
14 Runtime error 96 ms 131072 KB Execution killed with signal 9
15 Runtime error 114 ms 131072 KB Execution killed with signal 9
16 Runtime error 85 ms 131072 KB Execution killed with signal 9
17 Runtime error 83 ms 131072 KB Execution killed with signal 9