oj.uz

Submission #163710

# Submission time Handle Problem Language Result Execution time Memory
163710 2019-11-14T18:32:22 Z dolphingarlic Regions (IOI09_regions) C++14
85 / 100
 8000 ms 69528 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#pragma GCC Optimize("unroll-loops")
#pragma GCC target ("sse4")
#pragma GCC target("avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
 
const int c = 600;
 
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[200000 / c][25001], ans2[25001][200000 / 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:45: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:58: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:59: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:62: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:82: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 11 ms 9592 KB Output is correct
4 Correct 13 ms 9464 KB Output is correct
5 Correct 22 ms 9592 KB Output is correct
6 Correct 34 ms 9592 KB Output is correct
7 Correct 48 ms 9592 KB Output is correct
8 Correct 31 ms 9592 KB Output is correct
9 Correct 65 ms 10232 KB Output is correct
10 Correct 93 ms 10104 KB Output is correct
11 Correct 127 ms 10360 KB Output is correct
12 Correct 98 ms 11128 KB Output is correct
13 Correct 178 ms 10744 KB Output is correct
14 Correct 152 ms 11512 KB Output is correct
15 Correct 278 ms 15228 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 15812 KB Output is correct
2 Correct 1113 ms 14300 KB Output is correct
3 Correct 1966 ms 18236 KB Output is correct
4 Correct 344 ms 11384 KB Output is correct
5 Correct 456 ms 13688 KB Output is correct
6 Correct 865 ms 12692 KB Output is correct
7 Correct 1277 ms 13944 KB Output is correct
8 Correct 1263 ms 20752 KB Output is correct
9 Correct 2080 ms 20848 KB Output is correct
10 Correct 2793 ms 26812 KB Output is correct
11 Correct 3357 ms 19696 KB Output is correct
12 Correct 4415 ms 42592 KB Output is correct
13 Correct 5009 ms 43288 KB Output is correct
14 Execution timed out 8037 ms 49088 KB Time limit exceeded
15 Execution timed out 8045 ms 60804 KB Time limit exceeded
16 Correct 7033 ms 69528 KB Output is correct
17 Execution timed out 8035 ms 63144 KB Time limit exceeded