oj.uz

Submission #759348

# Submission time Handle Problem Language Result Execution time Memory
759348 2023-06-16T08:17:08 Z PanosPask Regions (IOI09_regions) C++14
100 / 100
 4340 ms 86912 KB 
#include <bits/stdc++.h>

using namespace std;

int N, R, Q;
int cutoff = 0;
vector<int> heavy_regions;
vector<bool> isheavy;
vector<int> home;
vector<int> ancestor_count;
vector<vector<int>> kids;
vector<vector<int>> total_subordinates;
vector<vector<int>> tin_by_region;
vector<vector<int>> id_by_region;

int counter = 0;
vector<int> tin;
vector<int> tout;

void dfs(int node)
{
    tin[node] = counter++;

    int r = home[node];
    tin_by_region[r].push_back(tin[node]);

    for (int i = 0; i < heavy_regions.size(); i++) {
        int curheavy = heavy_regions[i];

        total_subordinates[i][r] += ancestor_count[curheavy];
    }

    ancestor_count[r]++;
    for (auto kid : kids[node])
        dfs(kid);
    ancestor_count[r]--;

    tout[node] = counter;
}

int main(void)
{
    scanf("%d %d %d", &N, &R, &Q);

    cutoff = sqrt(N);

    kids.resize(N);
    home.resize(N);
    tin.resize(N);
    isheavy.resize(R);
    tout.resize(N);
    tin_by_region.resize(R);
    id_by_region.resize(R);

    scanf("%d", &home[0]);
    home[0]--;
    id_by_region[home[0]].push_back(0);
    for (int i = 1; i < N; i++) {
        int p, h;
        scanf("%d %d", &p, &h);
        p--; h--;

        kids[p].push_back(i);
        home[i] = h;
        id_by_region[h].push_back(i);
    }
    for (int i = 0; i < R; i++) {
        if (id_by_region[i].size() > cutoff) {
            isheavy[i] = true;
            heavy_regions.push_back(i);
        }
    }

    ancestor_count.resize(R);
    total_subordinates.resize(heavy_regions.size(), vector<int>(N));
    dfs(0);

    while (Q--) {
        int r1, r2;
        scanf("%d %d", &r1, &r2);
        r1--; r2--;

        int ans = 0;
        if (isheavy[r1]) {
            int pos = lower_bound(heavy_regions.begin(), heavy_regions.end(), r1) - heavy_regions.begin();

            ans = total_subordinates[pos][r2];
        }
        else {
            for (auto i : id_by_region[r1])
                ans += lower_bound(tin_by_region[r2].begin(), tin_by_region[r2].end(), tout[i])
                - lower_bound(tin_by_region[r2].begin(), tin_by_region[r2].end(), tin[i]);
        }

        printf("%d\n", ans);
        fflush(stdout);
    }

    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < heavy_regions.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:68:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if (id_by_region[i].size() > cutoff) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d %d", &N, &R, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d", &home[0]);
      |     ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d", &p, &h);
      |         ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d %d", &r1, &r2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 28 ms 336 KB Output is correct
8 Correct 32 ms 464 KB Output is correct
9 Correct 44 ms 848 KB Output is correct
10 Correct 68 ms 1060 KB Output is correct
11 Correct 115 ms 1488 KB Output is correct
12 Correct 125 ms 2084 KB Output is correct
13 Correct 145 ms 1828 KB Output is correct
14 Correct 201 ms 2984 KB Output is correct
15 Correct 223 ms 5572 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1634 ms 13544 KB Output is correct
2 Correct 2039 ms 9800 KB Output is correct
3 Correct 2599 ms 12396 KB Output is correct
4 Correct 239 ms 2864 KB Output is correct
5 Correct 320 ms 4720 KB Output is correct
6 Correct 542 ms 17064 KB Output is correct
7 Correct 977 ms 20264 KB Output is correct
8 Correct 996 ms 51404 KB Output is correct
9 Correct 2172 ms 14052 KB Output is correct
10 Correct 2760 ms 86912 KB Output is correct
11 Correct 4340 ms 15588 KB Output is correct
12 Correct 1245 ms 17744 KB Output is correct
13 Correct 1720 ms 17940 KB Output is correct
14 Correct 1739 ms 34032 KB Output is correct
15 Correct 2667 ms 22956 KB Output is correct
16 Correct 2556 ms 28252 KB Output is correct
17 Correct 2320 ms 43296 KB Output is correct