oj.uz

Submission #165711

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

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 9592 KB Output is correct
2 Correct 10 ms 9464 KB Output is correct
3 Correct 13 ms 9592 KB Output is correct
4 Correct 13 ms 9608 KB Output is correct
5 Correct 19 ms 9592 KB Output is correct
6 Correct 32 ms 9720 KB Output is correct
7 Correct 47 ms 9720 KB Output is correct
8 Correct 48 ms 9720 KB Output is correct
9 Correct 71 ms 10360 KB Output is correct
10 Correct 128 ms 10460 KB Output is correct
11 Correct 144 ms 10820 KB Output is correct
12 Correct 162 ms 11512 KB Output is correct
13 Correct 202 ms 11340 KB Output is correct
14 Correct 192 ms 12020 KB Output is correct
15 Correct 308 ms 15820 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 16152 KB Output is correct
2 Correct 1350 ms 14720 KB Output is correct
3 Correct 2177 ms 20396 KB Output is correct
4 Correct 339 ms 12588 KB Output is correct
5 Correct 510 ms 15484 KB Output is correct
6 Correct 765 ms 14384 KB Output is correct
7 Correct 1105 ms 14880 KB Output is correct
8 Correct 1348 ms 23976 KB Output is correct
9 Correct 2408 ms 26916 KB Output is correct
10 Correct 3596 ms 34372 KB Output is correct
11 Correct 3868 ms 28352 KB Output is correct
12 Correct 3990 ms 25200 KB Output is correct
13 Correct 4915 ms 27428 KB Output is correct
14 Correct 5494 ms 28224 KB Output is correct
15 Correct 6905 ms 35924 KB Output is correct
16 Correct 7509 ms 45456 KB Output is correct
17 Correct 6177 ms 43660 KB Output is correct