oj.uz

Submission #162852

# Submission time Handle Problem Language Result Execution time Memory
162852 2019-11-10T06:33:09 Z dolphingarlic Regions (IOI09_regions) C++14
85 / 100
 8000 ms 125344 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;

    Region() : ids(), ranges(), depth(0) {}
};

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});
}

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;
    cin >> n >> r >> q >> nodes[1].region;
    FOR(i, 2, n + 1) {
        int p;
        cin >> 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;
        cin >> a >> b;
        if (regions[a].ids.size() > c) cout << ans1[maps_to[a]][b] << endl;
        else if (regions[b].ids.size() > c) cout << ans2[a][maps_to[b]] << endl;
        else cout << query(regions[a], regions[b]) << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'll query(Region, Region)':
regions.cpp:46: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++) {
                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 16 ms 9464 KB Output is correct
5 Correct 19 ms 9464 KB Output is correct
6 Correct 37 ms 9592 KB Output is correct
7 Correct 27 ms 9592 KB Output is correct
8 Correct 38 ms 9592 KB Output is correct
9 Correct 72 ms 10232 KB Output is correct
10 Correct 113 ms 10104 KB Output is correct
11 Correct 133 ms 10488 KB Output is correct
12 Correct 188 ms 11132 KB Output is correct
13 Correct 221 ms 10744 KB Output is correct
14 Correct 175 ms 11540 KB Output is correct
15 Correct 257 ms 15224 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 16332 KB Output is correct
2 Correct 1330 ms 14832 KB Output is correct
3 Correct 1952 ms 18900 KB Output is correct
4 Correct 386 ms 11384 KB Output is correct
5 Correct 462 ms 13688 KB Output is correct
6 Correct 2458 ms 41020 KB Output is correct
7 Correct 1854 ms 50304 KB Output is correct
8 Correct 5064 ms 64492 KB Output is correct
9 Correct 2345 ms 20764 KB Output is correct
10 Correct 7594 ms 125344 KB Output is correct
11 Correct 3382 ms 19860 KB Output is correct
12 Correct 4784 ms 78312 KB Output is correct
13 Correct 5410 ms 78968 KB Output is correct
14 Execution timed out 8026 ms 95136 KB Time limit exceeded
15 Execution timed out 8010 ms 116616 KB Time limit exceeded
16 Correct 7573 ms 125276 KB Output is correct
17 Execution timed out 8018 ms 109312 KB Time limit exceeded