oj.uz

Submission #162863

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

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: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 11 ms 9464 KB Output is correct
2 Correct 10 ms 9464 KB Output is correct
3 Correct 12 ms 9464 KB Output is correct
4 Correct 13 ms 9464 KB Output is correct
5 Correct 14 ms 9464 KB Output is correct
6 Correct 35 ms 9468 KB Output is correct
7 Correct 46 ms 9592 KB Output is correct
8 Correct 47 ms 9592 KB Output is correct
9 Correct 37 ms 10232 KB Output is correct
10 Correct 62 ms 10100 KB Output is correct
11 Correct 149 ms 10364 KB Output is correct
12 Correct 167 ms 11128 KB Output is correct
13 Correct 209 ms 10744 KB Output is correct
14 Correct 244 ms 11384 KB Output is correct
15 Correct 317 ms 15224 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 15936 KB Output is correct
2 Correct 1263 ms 14552 KB Output is correct
3 Correct 1877 ms 18472 KB Output is correct
4 Correct 340 ms 11420 KB Output is correct
5 Correct 476 ms 13688 KB Output is correct
6 Correct 931 ms 12664 KB Output is correct
7 Correct 1324 ms 13864 KB Output is correct
8 Correct 1298 ms 20728 KB Output is correct
9 Correct 2043 ms 20692 KB Output is correct
10 Correct 2788 ms 26872 KB Output is correct
11 Correct 3178 ms 19828 KB Output is correct
12 Correct 4521 ms 56184 KB Output is correct
13 Correct 5051 ms 56992 KB Output is correct
14 Execution timed out 8009 ms 66560 KB Time limit exceeded
15 Execution timed out 8045 ms 82204 KB Time limit exceeded
16 Correct 7233 ms 90960 KB Output is correct
17 Execution timed out 8013 ms 80060 KB Time limit exceeded