oj.uz

Submission #162865

# Submission time Handle Problem Language Result Execution time Memory
162865 2019-11-10T07:10:43 Z dolphingarlic Regions (IOI09_regions) C++14
85 / 100
 8000 ms 83592 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 = 475;

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 10 ms 9464 KB Output is correct
3 Correct 14 ms 9464 KB Output is correct
4 Correct 17 ms 9592 KB Output is correct
5 Correct 20 ms 9592 KB Output is correct
6 Correct 36 ms 9592 KB Output is correct
7 Correct 44 ms 9592 KB Output is correct
8 Correct 49 ms 9592 KB Output is correct
9 Correct 42 ms 10232 KB Output is correct
10 Correct 105 ms 10104 KB Output is correct
11 Correct 136 ms 10360 KB Output is correct
12 Correct 154 ms 11156 KB Output is correct
13 Correct 167 ms 10744 KB Output is correct
14 Correct 188 ms 11384 KB Output is correct
15 Correct 229 ms 15224 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1181 ms 15936 KB Output is correct
2 Correct 1304 ms 14448 KB Output is correct
3 Correct 2041 ms 18388 KB Output is correct
4 Correct 320 ms 11384 KB Output is correct
5 Correct 419 ms 13688 KB Output is correct
6 Correct 2202 ms 27692 KB Output is correct
7 Correct 1233 ms 32616 KB Output is correct
8 Correct 3289 ms 41996 KB Output is correct
9 Correct 2001 ms 20748 KB Output is correct
10 Correct 2827 ms 26816 KB Output is correct
11 Correct 3139 ms 19720 KB Output is correct
12 Correct 4321 ms 51576 KB Output is correct
13 Correct 4962 ms 52300 KB Output is correct
14 Execution timed out 8015 ms 60624 KB Time limit exceeded
15 Execution timed out 8026 ms 74708 KB Time limit exceeded
16 Correct 7093 ms 83592 KB Output is correct
17 Execution timed out 8038 ms 74176 KB Time limit exceeded