oj.uz

Submission #163718

# Submission time Handle Problem Language Result Execution time Memory
163718 2019-11-14T19:01:58 Z dolphingarlic Regions (IOI09_regions) C++14
85 / 100
 8000 ms 81264 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#pragma GCC Optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int c = 450;

struct Node {
    int id, region, low, high;
    vector<int> children;
};
struct Region {
    vector<int> ids;
    vector<pair<int, int>> ranges;
    int depth;
};

Node nodes[200001];
Region regions[25001];

int ans1[450][25001], ans2[25001][450], maps_to[25001];

void dfs(int node, int& id_pool) {
    int id = id_pool++;
    int r = nodes[node].region;
    regions[r].ids.push_back(id);
    regions[r].depth++;
    regions[r].ranges.push_back({id_pool, regions[r].depth});

    for (int i : nodes[node].children) dfs(i, id_pool);
    regions[r].depth--;
    regions[r].ranges.push_back({id_pool, regions[r].depth});
}

inline int query(Region a, Region b) {
    if (a.ranges.empty()) return 0;

    int ans = 0, id = 0;
    while (id != b.ids.size() && b.ids[id] < a.ranges[0].first) id++;

    for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.size(); i++) {
        int pos2 = a.ranges[i + 1].first, depth = a.ranges[i].second;

        int old = id;
        while (id != b.ids.size() && b.ids[id] < pos2) id++;
        ans += depth * (id - old);
    }

    return ans;
}

int main() {
    int n, r, q;
    scanf("%d %d %d", &n, &r, &q);
    scanf("%d", &nodes[1].region);
    FOR(i, 2, n + 1) {
        int p;
        scanf("%d %d", &p, &nodes[i].region);
        nodes[p].children.push_back(i);
    }

    int id_pool = 1;
    dfs(1, id_pool);

    int cnt = 1;
    FOR(i, 1, r + 1) {
        if (regions[i].ids.size() > c) {
            FOR(j, 1, r + 1) {
                ans1[cnt][j] = query(regions[i], regions[j]);
                ans2[j][cnt] = query(regions[j], regions[i]);
            }
            maps_to[i] = cnt++;
        }
    }

    while (q--) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (regions[a].ids.size() > c)
            printf("%d\n", ans1[maps_to[a]][b]);
        else if (regions[b].ids.size() > c)
            printf("%d\n", ans2[a][maps_to[b]]);
        else
            printf("%d\n", query(regions[a], regions[b]));
        fflush(stdout);
    }
    return 0;
}

Compilation message

regions.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")
 
regions.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
regions.cpp: In function 'int query(Region, Region)':
regions.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (id != b.ids.size() && b.ids[id] < a.ranges[0].first) id++;
            ~~~^~~~~~~~~~~~~~~
regions.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:43:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.size(); i++) {
                                                ~~~^~~~~~~~~~~~~~~
regions.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (id != b.ids.size() && b.ids[id] < pos2) id++;
                ~~~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &r, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nodes[1].region);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &p, &nodes[i].region);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9464 KB Output is correct
2 Correct 10 ms 9464 KB Output is correct
3 Correct 11 ms 9592 KB Output is correct
4 Correct 12 ms 9464 KB Output is correct
5 Correct 21 ms 9464 KB Output is correct
6 Correct 33 ms 9640 KB Output is correct
7 Correct 61 ms 9512 KB Output is correct
8 Correct 48 ms 9788 KB Output is correct
9 Correct 41 ms 10148 KB Output is correct
10 Correct 66 ms 10040 KB Output is correct
11 Correct 137 ms 10404 KB Output is correct
12 Correct 125 ms 11128 KB Output is correct
13 Correct 152 ms 10772 KB Output is correct
14 Correct 232 ms 11384 KB Output is correct
15 Correct 231 ms 15224 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 15948 KB Output is correct
2 Correct 1302 ms 14464 KB Output is correct
3 Correct 1939 ms 18572 KB Output is correct
4 Correct 371 ms 11384 KB Output is correct
5 Correct 443 ms 13688 KB Output is correct
6 Correct 2187 ms 27020 KB Output is correct
7 Correct 1722 ms 32300 KB Output is correct
8 Correct 4661 ms 42856 KB Output is correct
9 Correct 2101 ms 20748 KB Output is correct
10 Correct 6821 ms 76100 KB Output is correct
11 Correct 3159 ms 19904 KB Output is correct
12 Correct 4396 ms 49984 KB Output is correct
13 Correct 4688 ms 50860 KB Output is correct
14 Execution timed out 8036 ms 58648 KB Time limit exceeded
15 Execution timed out 8026 ms 72340 KB Time limit exceeded
16 Correct 7042 ms 81264 KB Output is correct
17 Execution timed out 8045 ms 72372 KB Time limit exceeded