oj.uz

Submission #162858

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

const int c = 500;

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[500][25001], ans2[25001][500], 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:43: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: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);
         ~~~~~^~~~~~~~~~~~~~~~~

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 9464 KB Output is correct
3 Correct 13 ms 9464 KB Output is correct
4 Correct 12 ms 9464 KB Output is correct
5 Correct 20 ms 9592 KB Output is correct
6 Correct 20 ms 9592 KB Output is correct
7 Correct 52 ms 9592 KB Output is correct
8 Correct 47 ms 9592 KB Output is correct
9 Correct 41 ms 10232 KB Output is correct
10 Correct 109 ms 10104 KB Output is correct
11 Correct 144 ms 10360 KB Output is correct
12 Correct 183 ms 11128 KB Output is correct
13 Correct 196 ms 10748 KB Output is correct
14 Correct 249 ms 11384 KB Output is correct
15 Correct 293 ms 15228 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 15948 KB Output is correct
2 Correct 1321 ms 14440 KB Output is correct
3 Correct 2053 ms 18464 KB Output is correct
4 Correct 256 ms 11384 KB Output is correct
5 Correct 247 ms 13748 KB Output is correct
6 Correct 715 ms 12644 KB Output is correct
7 Correct 1093 ms 13888 KB Output is correct
8 Correct 949 ms 20712 KB Output is correct
9 Correct 1712 ms 20648 KB Output is correct
10 Correct 2204 ms 26884 KB Output is correct
11 Correct 3188 ms 19824 KB Output is correct
12 Correct 4527 ms 52972 KB Output is correct
13 Correct 4886 ms 53832 KB Output is correct
14 Execution timed out 8042 ms 62712 KB Time limit exceeded
15 Execution timed out 8054 ms 77292 KB Time limit exceeded
16 Correct 7483 ms 85956 KB Output is correct
17 Execution timed out 8007 ms 76244 KB Time limit exceeded