oj.uz

Submission #638598

# Submission time Handle Problem Language Result Execution time Memory
638598 2022-09-06T12:56:21 Z BhavayGoyal Regions (IOI09_regions) C++14
13 / 100
 1400 ms 93256 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};


// -------------------------------------------------- Main Code --------------------------------------------------

const int N = 2e5+5, R = 25000+5;
vi g[N], members[R];
int region[R], tin[N], tout[N], tarr[8*N], timer = 1;

struct segTree {
    int n;
    vector<unordered_map<int, int>> tree;
    segTree (int N) {n = 1; while (n < N) n *= 2; tree = vector<unordered_map<int, int>>(2*n+2);}
 
    void build(int node, int left, int right, int arr[]) {
        if (left == right) {if (arr[left] != -1) tree[node][arr[left]]++; return;}
        build(node*2, left, (left+right)/2, arr);
        build(node*2+1, (left+right)/2+1, right, arr);
        for (auto i : tree[node*2]) tree[node][i.f] += i.s;
        for (auto i : tree[node*2+1]) tree[node][i.f] += i.s;
    }
    void build(int arr[]) {build(1, 1, n, arr);}
 
    int query(int node, int left, int right, int l, int r, int val) {
        if (left > r || right < l) return 0;
        else if (left >= l && right <= r) return tree[node][val];
        else return query(node*2, left, (left+right)/2, l, r, val) + query(node*2+1, (left+right)/2+1, right, l, r, val);
    }
    int query(int left, int right, int val) {return query(1, 1, n, left, right, val);}
};

void dfs(int src, int par) {
    tarr[timer] = region[src];
    tin[src] = timer++;
    for (auto ch : g[src]) if (ch != par) dfs(ch, src);
    tout[src] = timer-1;
}

vi largeregions;
vii preProcessing;

void dfs2(int src, int par, int i, int ct = 0) {
    for (auto ch : g[src]) {
        if (ch == par) continue;
        preProcessing[i][region[ch]] += ct;
        dfs2(ch, src, i, ct+(largeregions[i]==region[ch]));
    }
}

void sol() {
    int n, r, q; cin >> n >> r >> q;
    int sqn = sqrt(n)+1;
    for (int i = 1; i <= n; i++) {
        if (i == 1) cin >> region[i];
        else {
            int x; cin >> x >> region[i];
            g[i].pb(x);
            g[x].pb(i);
        }
        members[region[i]].pb(i);
    }

    dfs(1, -1);
    segTree tree(n); tree.build(tarr);

    for (int i = 1; i <= r; i++) if (members[i].size() >= sqn) largeregions.pb(i);
    preProcessing = vii(largeregions.size(), vi(r+1, 0));
    for (int i = 0; i < largeregions.size(); i++) dfs2(1, -1, i, (largeregions[i]==region[1]));

    while (q--) {
        int a, b; cin >> a >> b;
        int idx = lower_bound(all(largeregions), a) - largeregions.begin();
        if (idx < largeregions.size() && largeregions[idx] == a) {
            cout << preProcessing[idx][b] << endl;
            continue;
        }

        int ans = 0;
        for (auto ch : members[a]) ans += tree.query(tin[ch], tout[ch], b);
        cout << ans << endl;
    }
}

int main () {
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void sol()':
regions.cpp:93:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |     for (int i = 1; i <= r; i++) if (members[i].size() >= sqn) largeregions.pb(i);
      |                                      ~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < largeregions.size(); i++) dfs2(1, -1, i, (largeregions[i]==region[1]));
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         if (idx < largeregions.size() && largeregions[idx] == a) {
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 7 ms 5840 KB Output is correct
5 Correct 13 ms 6320 KB Output is correct
6 Correct 27 ms 6904 KB Output is correct
7 Correct 35 ms 9260 KB Output is correct
8 Correct 56 ms 10376 KB Output is correct
9 Correct 155 ms 19368 KB Output is correct
10 Correct 340 ms 35492 KB Output is correct
11 Correct 1089 ms 66180 KB Output is correct
12 Correct 1400 ms 82104 KB Output is correct
13 Correct 1330 ms 93256 KB Output is correct
14 Runtime error 21 ms 13168 KB Execution killed with signal 11
15 Runtime error 21 ms 13128 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 13240 KB Execution killed with signal 11
2 Runtime error 21 ms 13252 KB Execution killed with signal 11
3 Runtime error 21 ms 13204 KB Execution killed with signal 11
4 Runtime error 27 ms 13260 KB Execution killed with signal 11
5 Runtime error 22 ms 13264 KB Execution killed with signal 11
6 Runtime error 23 ms 13400 KB Execution killed with signal 11
7 Runtime error 24 ms 13712 KB Execution killed with signal 11
8 Runtime error 27 ms 13376 KB Execution killed with signal 11
9 Runtime error 28 ms 13428 KB Execution killed with signal 11
10 Runtime error 29 ms 13540 KB Execution killed with signal 11
11 Runtime error 23 ms 13596 KB Execution killed with signal 11
12 Runtime error 22 ms 13484 KB Execution killed with signal 11
13 Runtime error 23 ms 13512 KB Execution killed with signal 11
14 Runtime error 22 ms 13368 KB Execution killed with signal 11
15 Runtime error 28 ms 13512 KB Execution killed with signal 11
16 Runtime error 23 ms 13500 KB Execution killed with signal 11
17 Runtime error 23 ms 13512 KB Execution killed with signal 11