oj.uz

Submission #638600

# Submission time Handle Problem Language Result Execution time Memory
638600 2022-09-06T12:57:23 Z BhavayGoyal Regions (IOI09_regions) C++14
0 / 100
 168 ms 24472 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:79:9: warning: unused variable 'sqn' [-Wunused-variable]
   79 |     int sqn = sqrt(n)+1;
      |         ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
2 Incorrect 4 ms 5584 KB Unexpected end of file - int32 expected
3 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
4 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
5 Incorrect 4 ms 5584 KB Unexpected end of file - int32 expected
6 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
7 Incorrect 4 ms 5584 KB Unexpected end of file - int32 expected
8 Incorrect 4 ms 5584 KB Unexpected end of file - int32 expected
9 Incorrect 6 ms 5712 KB Unexpected end of file - int32 expected
10 Incorrect 9 ms 5908 KB Unexpected end of file - int32 expected
11 Incorrect 10 ms 6096 KB Unexpected end of file - int32 expected
12 Incorrect 15 ms 6224 KB Unexpected end of file - int32 expected
13 Incorrect 17 ms 6340 KB Unexpected end of file - int32 expected
14 Runtime error 27 ms 13148 KB Execution killed with signal 11
15 Runtime error 29 ms 13856 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 16036 KB Execution killed with signal 11
2 Runtime error 50 ms 16584 KB Execution killed with signal 11
3 Runtime error 60 ms 16916 KB Execution killed with signal 11
4 Runtime error 27 ms 13216 KB Execution killed with signal 11
5 Runtime error 38 ms 13552 KB Execution killed with signal 11
6 Runtime error 38 ms 14592 KB Execution killed with signal 11
7 Runtime error 47 ms 15688 KB Execution killed with signal 11
8 Runtime error 68 ms 17608 KB Execution killed with signal 11
9 Runtime error 116 ms 20828 KB Execution killed with signal 11
10 Runtime error 115 ms 22088 KB Execution killed with signal 11
11 Runtime error 157 ms 24472 KB Execution killed with signal 11
12 Runtime error 149 ms 23368 KB Execution killed with signal 11
13 Runtime error 122 ms 23408 KB Execution killed with signal 11
14 Runtime error 128 ms 24036 KB Execution killed with signal 11
15 Runtime error 127 ms 23920 KB Execution killed with signal 11
16 Runtime error 168 ms 23912 KB Execution killed with signal 11
17 Runtime error 141 ms 23972 KB Execution killed with signal 11