oj.uz

Submission #165712

# Submission time Handle Problem Language Result Execution time Memory
165712 2019-11-28T11:15:53 Z dolphingarlic Regions (IOI09_regions) C++14
100 / 100
 7148 ms 43900 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 = 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];

unordered_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);

    while (q--) {
        int a, b;
        scanf("%d %d", &a, &b);
        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

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:69: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 10 ms 9464 KB Output is correct
2 Correct 12 ms 9596 KB Output is correct
3 Correct 12 ms 9592 KB Output is correct
4 Correct 15 ms 9512 KB Output is correct
5 Correct 14 ms 9556 KB Output is correct
6 Correct 31 ms 9692 KB Output is correct
7 Correct 46 ms 9716 KB Output is correct
8 Correct 47 ms 9836 KB Output is correct
9 Correct 70 ms 10332 KB Output is correct
10 Correct 61 ms 10384 KB Output is correct
11 Correct 137 ms 10756 KB Output is correct
12 Correct 163 ms 11416 KB Output is correct
13 Correct 111 ms 11376 KB Output is correct
14 Correct 216 ms 11716 KB Output is correct
15 Correct 237 ms 15736 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 16272 KB Output is correct
2 Correct 1233 ms 14828 KB Output is correct
3 Correct 1689 ms 20200 KB Output is correct
4 Correct 307 ms 12448 KB Output is correct
5 Correct 358 ms 15204 KB Output is correct
6 Correct 623 ms 14128 KB Output is correct
7 Correct 921 ms 14664 KB Output is correct
8 Correct 1130 ms 23716 KB Output is correct
9 Correct 1886 ms 26408 KB Output is correct
10 Correct 2838 ms 33540 KB Output is correct
11 Correct 3006 ms 27116 KB Output is correct
12 Correct 4030 ms 24452 KB Output is correct
13 Correct 4929 ms 27664 KB Output is correct
14 Correct 5470 ms 27412 KB Output is correct
15 Correct 6906 ms 34864 KB Output is correct
16 Correct 7148 ms 43900 KB Output is correct
17 Correct 5668 ms 42052 KB Output is correct