oj.uz

Submission #638603

# Submission time Handle Problem Language Result Execution time Memory
638603 2022-09-06T13:01:21 Z BhavayGoyal Regions (IOI09_regions) C++14
0 / 100
 128 ms 11336 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 2 ms 5584 KB Unexpected end of file - int32 expected
3 Incorrect 2 ms 5584 KB Unexpected end of file - int32 expected
4 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
5 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
6 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
7 Incorrect 5 ms 5584 KB Unexpected end of file - int32 expected
8 Incorrect 4 ms 5584 KB Unexpected end of file - int32 expected
9 Incorrect 5 ms 5584 KB Unexpected end of file - int32 expected
10 Incorrect 7 ms 5584 KB Unexpected end of file - int32 expected
11 Incorrect 12 ms 5584 KB Unexpected end of file - int32 expected
12 Incorrect 12 ms 5608 KB Unexpected end of file - int32 expected
13 Incorrect 15 ms 5584 KB Unexpected end of file - int32 expected
14 Runtime error 20 ms 11224 KB Execution killed with signal 11
15 Runtime error 25 ms 11336 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 11240 KB Execution killed with signal 11
2 Runtime error 41 ms 11280 KB Execution killed with signal 11
3 Runtime error 47 ms 11312 KB Execution killed with signal 11
4 Runtime error 27 ms 11204 KB Execution killed with signal 11
5 Runtime error 25 ms 11316 KB Execution killed with signal 11
6 Runtime error 36 ms 11308 KB Execution killed with signal 11
7 Runtime error 44 ms 11296 KB Execution killed with signal 11
8 Runtime error 58 ms 11312 KB Execution killed with signal 11
9 Runtime error 80 ms 11300 KB Execution killed with signal 11
10 Runtime error 92 ms 11224 KB Execution killed with signal 11
11 Runtime error 111 ms 11208 KB Execution killed with signal 11
12 Runtime error 106 ms 11308 KB Execution killed with signal 11
13 Runtime error 128 ms 11284 KB Execution killed with signal 11
14 Runtime error 106 ms 11292 KB Execution killed with signal 11
15 Runtime error 120 ms 11296 KB Execution killed with signal 11
16 Runtime error 110 ms 11300 KB Execution killed with signal 11
17 Runtime error 114 ms 11296 KB Execution killed with signal 11