oj.uz

Submission #162868

# Submission time Handle Problem Language Result Execution time Memory
162868 2019-11-10T07:14:09 Z dolphingarlic Regions (IOI09_regions) C++14
75 / 100
 8000 ms 61632 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#pragma GCC Optimize("unroll-loops")
#pragma GCC target ("sse4")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int c = 250;

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[c][25001], ans2[25001][c], 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;
    vector<int>::iterator id = b.ids.begin();
    while (id != b.ids.end() && *id < a.ranges[0].first) id++;

    for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.end(); i++) {
        int pos2 = a.ranges[i + 1].first, depth = a.ranges[i].second;

        vector<int>::iterator old = id;
        while (id != b.ids.end() && *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("O3")
 
regions.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")
 
regions.cpp: In function 'int query(Region, Region)':
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.end(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~~
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 10 ms 9464 KB Output is correct
2 Correct 11 ms 9592 KB Output is correct
3 Correct 13 ms 9592 KB Output is correct
4 Correct 13 ms 9464 KB Output is correct
5 Correct 18 ms 9464 KB Output is correct
6 Correct 27 ms 9596 KB Output is correct
7 Correct 44 ms 9592 KB Output is correct
8 Correct 31 ms 9720 KB Output is correct
9 Correct 67 ms 10244 KB Output is correct
10 Correct 62 ms 10112 KB Output is correct
11 Correct 76 ms 10408 KB Output is correct
12 Correct 87 ms 11160 KB Output is correct
13 Correct 183 ms 10704 KB Output is correct
14 Correct 231 ms 11492 KB Output is correct
15 Correct 270 ms 15356 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 15776 KB Output is correct
2 Correct 1064 ms 14552 KB Output is correct
3 Correct 1596 ms 18184 KB Output is correct
4 Correct 219 ms 11440 KB Output is correct
5 Correct 252 ms 13728 KB Output is correct
6 Correct 2159 ms 21460 KB Output is correct
7 Correct 2550 ms 25988 KB Output is correct
8 Correct 4282 ms 34948 KB Output is correct
9 Correct 6285 ms 41796 KB Output is correct
10 Execution timed out 8061 ms 60616 KB Time limit exceeded
11 Execution timed out 8021 ms 55440 KB Time limit exceeded
12 Correct 4504 ms 37420 KB Output is correct
13 Correct 4436 ms 38076 KB Output is correct
14 Execution timed out 8019 ms 43020 KB Time limit exceeded
15 Execution timed out 8019 ms 52572 KB Time limit exceeded
16 Correct 6994 ms 61632 KB Output is correct
17 Execution timed out 8009 ms 56640 KB Time limit exceeded