oj.uz

답안 #1103757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103757 2024-10-21T15:49:37 Z salmon Regions (IOI09_regions) C++14
55 / 100
 2469 ms 131076 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 = 5001;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22864 KB Output is correct
2 Correct 4 ms 22864 KB Output is correct
3 Correct 6 ms 22864 KB Output is correct
4 Correct 10 ms 22864 KB Output is correct
5 Correct 9 ms 22864 KB Output is correct
6 Correct 17 ms 23120 KB Output is correct
7 Correct 27 ms 23120 KB Output is correct
8 Correct 24 ms 23120 KB Output is correct
9 Correct 42 ms 23632 KB Output is correct
10 Correct 79 ms 23376 KB Output is correct
11 Correct 112 ms 23912 KB Output is correct
12 Correct 125 ms 24656 KB Output is correct
13 Correct 151 ms 24144 KB Output is correct
14 Correct 168 ms 24656 KB Output is correct
15 Correct 200 ms 29008 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1210 ms 131072 KB Execution killed with signal 9
2 Runtime error 395 ms 131072 KB Execution killed with signal 9
3 Runtime error 406 ms 131072 KB Execution killed with signal 9
4 Correct 217 ms 25004 KB Output is correct
5 Correct 340 ms 27720 KB Output is correct
6 Correct 646 ms 26448 KB Output is correct
7 Correct 964 ms 27728 KB Output is correct
8 Correct 896 ms 35744 KB Output is correct
9 Correct 1491 ms 34120 KB Output is correct
10 Correct 2012 ms 42824 KB Output is correct
11 Correct 2469 ms 33608 KB Output is correct
12 Runtime error 460 ms 131072 KB Execution killed with signal 9
13 Runtime error 437 ms 131072 KB Execution killed with signal 9
14 Runtime error 414 ms 131072 KB Execution killed with signal 9
15 Runtime error 428 ms 131076 KB Execution killed with signal 9
16 Runtime error 415 ms 131072 KB Execution killed with signal 9
17 Runtime error 513 ms 131076 KB Execution killed with signal 9