oj.uz

Submission #163716

# Submission time Handle Problem Language Result Execution time Memory
163716 2019-11-14T18:59:43 Z dolphingarlic Regions (IOI09_regions) C++14
85 / 100
 8000 ms 73296 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 = 550;

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[370][25001], ans2[25001][370], 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;
    int 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:42: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:44: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:44: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:48: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:57: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:58: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:61: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:81: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 16 ms 9592 KB Output is correct
2 Correct 10 ms 9596 KB Output is correct
3 Correct 12 ms 9464 KB Output is correct
4 Correct 15 ms 9596 KB Output is correct
5 Correct 17 ms 9464 KB Output is correct
6 Correct 21 ms 9592 KB Output is correct
7 Correct 46 ms 9592 KB Output is correct
8 Correct 27 ms 9592 KB Output is correct
9 Correct 67 ms 10232 KB Output is correct
10 Correct 108 ms 10104 KB Output is correct
11 Correct 146 ms 10412 KB Output is correct
12 Correct 155 ms 11128 KB Output is correct
13 Correct 201 ms 10744 KB Output is correct
14 Correct 244 ms 11384 KB Output is correct
15 Correct 262 ms 15100 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1156 ms 15752 KB Output is correct
2 Correct 1231 ms 14452 KB Output is correct
3 Correct 1864 ms 18336 KB Output is correct
4 Correct 323 ms 11384 KB Output is correct
5 Correct 402 ms 13688 KB Output is correct
6 Correct 954 ms 12792 KB Output is correct
7 Correct 1279 ms 14072 KB Output is correct
8 Correct 1049 ms 20728 KB Output is correct
9 Correct 1992 ms 20728 KB Output is correct
10 Correct 2880 ms 26848 KB Output is correct
11 Correct 3156 ms 19852 KB Output is correct
12 Correct 4337 ms 44924 KB Output is correct
13 Correct 4636 ms 45704 KB Output is correct
14 Execution timed out 8025 ms 52328 KB Time limit exceeded
15 Execution timed out 8048 ms 64348 KB Time limit exceeded
16 Correct 7102 ms 73296 KB Output is correct
17 Execution timed out 8041 ms 65764 KB Time limit exceeded