Submission #165709

#	Time	Username	Problem	Language	Result	Execution time	Memory
165709		dolphingarlic	Regions (IOI09_regions)	C++14	85 / 100	8020 ms	85248 KiB

regions

#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 = 750;

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];
map<int, int> cache;

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 if (cache.find(25000 * a + b) != cache.end())
            printf("%d\n", cache[25000 * a + b]);
        else {
            int q = query(regions[a], regions[b]);
            printf("%d\n", q);
            cache[25000 * a + b] = q;
        }
        fflush(stdout);
    }
    return 0;
}

Compilation message (stderr)

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 / 15
• Subtask 2: 70 / 85