oj.uz

답안 #638608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638608 2022-09-06T13:07:27 Z BhavayGoyal Regions (IOI09_regions) C++14
0 / 100
 1435 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;
        }

        cout << -1 << endl;

        // 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9688 KB Output isn't correct
2 Incorrect 6 ms 9680 KB Output isn't correct
3 Incorrect 6 ms 9680 KB Output isn't correct
4 Incorrect 10 ms 9808 KB Output isn't correct
5 Incorrect 12 ms 9936 KB Output isn't correct
6 Incorrect 25 ms 10320 KB Output isn't correct
7 Incorrect 20 ms 10960 KB Output isn't correct
8 Incorrect 34 ms 11088 KB Output isn't correct
9 Incorrect 39 ms 14800 KB Output isn't correct
10 Incorrect 102 ms 19760 KB Output isn't correct
11 Incorrect 109 ms 21056 KB Output isn't correct
12 Incorrect 91 ms 29980 KB Output isn't correct
13 Incorrect 174 ms 30792 KB Output isn't correct
14 Incorrect 202 ms 31780 KB Output isn't correct
15 Incorrect 244 ms 51828 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 757 ms 80960 KB Output isn't correct
2 Incorrect 784 ms 81100 KB Output isn't correct
3 Incorrect 1435 ms 88392 KB Output isn't correct
4 Incorrect 280 ms 35020 KB Output isn't correct
5 Incorrect 414 ms 52316 KB Output isn't correct
6 Incorrect 648 ms 58312 KB Output isn't correct
7 Incorrect 1116 ms 97064 KB Output isn't correct
8 Incorrect 1169 ms 112292 KB Output isn't correct
9 Runtime error 242 ms 131072 KB Execution killed with signal 9
10 Runtime error 260 ms 131072 KB Execution killed with signal 9
11 Runtime error 285 ms 131072 KB Execution killed with signal 9
12 Runtime error 282 ms 131072 KB Execution killed with signal 9
13 Runtime error 273 ms 131072 KB Execution killed with signal 9
14 Runtime error 287 ms 131072 KB Execution killed with signal 9
15 Runtime error 282 ms 131072 KB Execution killed with signal 9
16 Runtime error 255 ms 131072 KB Execution killed with signal 9
17 Runtime error 264 ms 131072 KB Execution killed with signal 9