oj.uz

Submission #638607

# Submission time Handle Problem Language Result Execution time Memory
638607 2022-09-06T13:03:42 Z BhavayGoyal Regions (IOI09_regions) C++14
0 / 100
 464 ms 131072 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;
vi g[N], members[N];
int region[N], 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 9680 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 9680 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 9680 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 9808 KB Time limit exceeded (wall clock)
5 Execution timed out 5 ms 9936 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 10320 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 10960 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 11088 KB Time limit exceeded (wall clock)
9 Execution timed out 16 ms 14800 KB Time limit exceeded (wall clock)
10 Execution timed out 27 ms 19704 KB Time limit exceeded (wall clock)
11 Execution timed out 33 ms 21064 KB Time limit exceeded (wall clock)
12 Execution timed out 50 ms 29952 KB Time limit exceeded (wall clock)
13 Execution timed out 55 ms 30864 KB Time limit exceeded (wall clock)
14 Execution timed out 63 ms 31828 KB Time limit exceeded (wall clock)
15 Execution timed out 87 ms 51868 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 208 ms 80968 KB Time limit exceeded (wall clock)
2 Execution timed out 201 ms 81028 KB Time limit exceeded (wall clock)
3 Execution timed out 232 ms 88296 KB Time limit exceeded (wall clock)
4 Execution timed out 82 ms 35068 KB Time limit exceeded (wall clock)
5 Execution timed out 107 ms 52296 KB Time limit exceeded (wall clock)
6 Execution timed out 189 ms 58316 KB Time limit exceeded (wall clock)
7 Execution timed out 303 ms 97080 KB Time limit exceeded (wall clock)
8 Execution timed out 464 ms 112496 KB Time limit exceeded (wall clock)
9 Runtime error 311 ms 131072 KB Execution killed with signal 9
10 Runtime error 322 ms 131072 KB Execution killed with signal 9
11 Runtime error 340 ms 131072 KB Execution killed with signal 9
12 Runtime error 335 ms 131072 KB Execution killed with signal 9
13 Runtime error 323 ms 131072 KB Execution killed with signal 9
14 Runtime error 338 ms 131072 KB Execution killed with signal 9
15 Runtime error 335 ms 131072 KB Execution killed with signal 9
16 Runtime error 306 ms 131072 KB Execution killed with signal 9
17 Runtime error 325 ms 131072 KB Execution killed with signal 9