oj.uz

답안 #638593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638593 2022-09-06T12:53:03 Z BhavayGoyal Regions (IOI09_regions) C++14
18 / 100
 1819 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+2;
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
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 6 ms 9680 KB Output is correct
3 Correct 7 ms 9680 KB Output is correct
4 Correct 10 ms 9936 KB Output is correct
5 Correct 17 ms 10424 KB Output is correct
6 Correct 25 ms 11044 KB Output is correct
7 Correct 47 ms 13360 KB Output is correct
8 Correct 66 ms 14500 KB Output is correct
9 Correct 150 ms 23412 KB Output is correct
10 Correct 327 ms 39560 KB Output is correct
11 Correct 1092 ms 70472 KB Output is correct
12 Correct 1392 ms 86088 KB Output is correct
13 Correct 1371 ms 97460 KB Output is correct
14 Runtime error 1819 ms 131072 KB Execution killed with signal 9
15 Runtime error 1505 ms 131072 KB Execution killed with signal 9

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1125 ms 131072 KB Execution killed with signal 9
2 Runtime error 1039 ms 131072 KB Execution killed with signal 9
3 Runtime error 891 ms 131072 KB Execution killed with signal 9
4 Runtime error 1530 ms 131072 KB Execution killed with signal 9
5 Runtime error 1419 ms 131072 KB Execution killed with signal 9
6 Correct 1125 ms 77012 KB Output is correct
7 Runtime error 967 ms 131072 KB Execution killed with signal 9
8 Runtime error 716 ms 131072 KB Execution killed with signal 9
9 Runtime error 272 ms 131072 KB Execution killed with signal 9
10 Runtime error 286 ms 131072 KB Execution killed with signal 9
11 Runtime error 305 ms 131072 KB Execution killed with signal 9
12 Runtime error 302 ms 131072 KB Execution killed with signal 9
13 Runtime error 302 ms 131072 KB Execution killed with signal 9
14 Runtime error 302 ms 131072 KB Execution killed with signal 9
15 Runtime error 287 ms 131072 KB Execution killed with signal 9
16 Runtime error 292 ms 131072 KB Execution killed with signal 9
17 Runtime error 289 ms 131072 KB Execution killed with signal 9