oj.uz

답안 #638594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638594 2022-09-06T12:54:27 Z BhavayGoyal Regions (IOI09_regions) C++14
0 / 100
 62 ms 26752 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+2, R = 25000+2;
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]));
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5584 KB Unexpected end of file - int32 expected
2 Incorrect 3 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 5712 KB Unexpected end of file - int32 expected
5 Incorrect 3 ms 5840 KB Unexpected end of file - int32 expected
6 Incorrect 5 ms 6224 KB Unexpected end of file - int32 expected
7 Incorrect 5 ms 6736 KB Unexpected end of file - int32 expected
8 Incorrect 6 ms 6992 KB Unexpected end of file - int32 expected
9 Incorrect 14 ms 10660 KB Unexpected end of file - int32 expected
10 Incorrect 28 ms 15568 KB Unexpected end of file - int32 expected
11 Incorrect 34 ms 16976 KB Unexpected end of file - int32 expected
12 Incorrect 53 ms 25856 KB Unexpected end of file - int32 expected
13 Incorrect 62 ms 26752 KB Unexpected end of file - int32 expected
14 Runtime error 29 ms 13196 KB Execution killed with signal 11
15 Runtime error 21 ms 13136 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 22 ms 13232 KB Execution killed with signal 11
2 Runtime error 22 ms 13264 KB Execution killed with signal 11
3 Runtime error 28 ms 13208 KB Execution killed with signal 11
4 Runtime error 28 ms 13308 KB Execution killed with signal 11
5 Runtime error 22 ms 13256 KB Execution killed with signal 11
6 Runtime error 26 ms 13364 KB Execution killed with signal 11
7 Runtime error 25 ms 13512 KB Execution killed with signal 11
8 Runtime error 26 ms 13352 KB Execution killed with signal 11
9 Runtime error 24 ms 13392 KB Execution killed with signal 11
10 Runtime error 28 ms 13452 KB Execution killed with signal 11
11 Runtime error 31 ms 13536 KB Execution killed with signal 11
12 Runtime error 23 ms 13428 KB Execution killed with signal 11
13 Runtime error 25 ms 13508 KB Execution killed with signal 11
14 Runtime error 29 ms 13432 KB Execution killed with signal 11
15 Runtime error 33 ms 13488 KB Execution killed with signal 11
16 Runtime error 25 ms 13460 KB Execution killed with signal 11
17 Runtime error 23 ms 13520 KB Execution killed with signal 11