oj.uz

Submission #162854

# Submission time Handle Problem Language Result Execution time Memory
162854 2019-11-10T06:40:17 Z dolphingarlic Regions (IOI09_regions) C++14
85 / 100
 8000 ms 125412 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
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];

ll ans1[450][25001], ans2[25001][450];
int 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 ll query(Region a, Region b) {
    if (a.ranges.empty()) return 0;

    ll 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;
        ll 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: In function 'll 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:82:74: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
         if (regions[a].ids.size() > c) printf("%d\n", ans1[maps_to[a]][b]);
                                                       ~~~~~~~~~~~~~~~~~~~^
regions.cpp:83:79: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
         else if (regions[b].ids.size() > c) printf("%d\n", ans2[a][maps_to[b]]);
                                                            ~~~~~~~~~~~~~~~~~~~^
regions.cpp:84:58: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
         else printf("%d\n", query(regions[a], regions[b]));
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
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 9592 KB Output is correct
3 Correct 13 ms 9464 KB Output is correct
4 Correct 17 ms 9464 KB Output is correct
5 Correct 22 ms 9512 KB Output is correct
6 Correct 22 ms 9720 KB Output is correct
7 Correct 33 ms 9592 KB Output is correct
8 Correct 44 ms 9592 KB Output is correct
9 Correct 62 ms 10232 KB Output is correct
10 Correct 84 ms 10104 KB Output is correct
11 Correct 131 ms 10364 KB Output is correct
12 Correct 152 ms 11128 KB Output is correct
13 Correct 217 ms 10744 KB Output is correct
14 Correct 153 ms 11388 KB Output is correct
15 Correct 182 ms 15224 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 16256 KB Output is correct
2 Correct 1280 ms 14848 KB Output is correct
3 Correct 1927 ms 18796 KB Output is correct
4 Correct 323 ms 11384 KB Output is correct
5 Correct 384 ms 13688 KB Output is correct
6 Correct 2298 ms 41084 KB Output is correct
7 Correct 1849 ms 50236 KB Output is correct
8 Correct 4838 ms 64372 KB Output is correct
9 Correct 2173 ms 20656 KB Output is correct
10 Correct 7016 ms 125412 KB Output is correct
11 Correct 3113 ms 19812 KB Output is correct
12 Correct 4738 ms 78240 KB Output is correct
13 Correct 5059 ms 79072 KB Output is correct
14 Execution timed out 8073 ms 95596 KB Time limit exceeded
15 Execution timed out 8010 ms 116472 KB Time limit exceeded
16 Correct 7178 ms 125376 KB Output is correct
17 Execution timed out 8023 ms 109344 KB Time limit exceeded