Submission #163719

# Submission time Handle Problem Language Result Execution time Memory
163719 2019-11-14T19:04:23 Z dolphingarlic Regions (IOI09_regions) C++14
26 / 100
1961 ms 97968 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);
         ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 26 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 26 ms 19104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 14 ms 9464 KB Output is correct
5 Correct 21 ms 9592 KB Output is correct
6 Runtime error 27 ms 19368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 46 ms 9592 KB Output is correct
8 Correct 50 ms 9720 KB Output is correct
9 Correct 65 ms 10232 KB Output is correct
10 Correct 80 ms 10104 KB Output is correct
11 Correct 117 ms 10360 KB Output is correct
12 Correct 135 ms 11172 KB Output is correct
13 Correct 188 ms 10792 KB Output is correct
14 Correct 175 ms 11512 KB Output is correct
15 Correct 249 ms 15236 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1164 ms 15936 KB Output is correct
2 Correct 1270 ms 14404 KB Output is correct
3 Correct 1961 ms 18412 KB Output is correct
4 Runtime error 45 ms 23032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 52 ms 27640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 59 ms 25592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 70 ms 28280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 169 ms 73904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 136 ms 41872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 146 ms 54428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 155 ms 39928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 161 ms 42864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 156 ms 44208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 198 ms 42592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 1534 ms 97968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 198 ms 74676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 175 ms 70032 KB Execution killed with signal 11 (could be triggered by violating memory limits)