oj.uz

Submission #638612

# Submission time Handle Problem Language Result Execution time Memory
638612 2022-09-06T13:29:38 Z BhavayGoyal Regions (IOI09_regions) C++14
100 / 100
 4380 ms 44652 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], arr[N];
int region[N], tin[N], tout[N], tarr[N], timer = 1;

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);

    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]));

    for (int i = 1; i <= n; i++) arr[tarr[i]].pb(i);

    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 += (upper_bound(all(arr[b]), tout[ch]) - lower_bound(all(arr[b]), tin[ch]));
        }
        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:70:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     for (int i = 1; i <= r; i++) if (members[i].size() >= sqn) largeregions.pb(i);
      |                                      ~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < largeregions.size(); i++) dfs2(1, -1, i, (largeregions[i]==region[1]));
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         if (idx < largeregions.size() && largeregions[idx] == a) {
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 9 ms 14416 KB Output is correct
3 Correct 11 ms 14416 KB Output is correct
4 Correct 12 ms 14416 KB Output is correct
5 Correct 10 ms 14416 KB Output is correct
6 Correct 26 ms 14504 KB Output is correct
7 Correct 20 ms 14416 KB Output is correct
8 Correct 41 ms 14544 KB Output is correct
9 Correct 51 ms 14928 KB Output is correct
10 Correct 85 ms 14928 KB Output is correct
11 Correct 139 ms 15312 KB Output is correct
12 Correct 155 ms 15736 KB Output is correct
13 Correct 206 ms 15888 KB Output is correct
14 Correct 318 ms 16188 KB Output is correct
15 Correct 294 ms 20552 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1806 ms 20156 KB Output is correct
2 Correct 2041 ms 19288 KB Output is correct
3 Correct 2832 ms 22760 KB Output is correct
4 Correct 305 ms 16340 KB Output is correct
5 Correct 276 ms 17752 KB Output is correct
6 Correct 631 ms 19724 KB Output is correct
7 Correct 1276 ms 21192 KB Output is correct
8 Correct 1247 ms 30832 KB Output is correct
9 Correct 2236 ms 24788 KB Output is correct
10 Correct 3183 ms 43336 KB Output is correct
11 Correct 4380 ms 27312 KB Output is correct
12 Correct 1466 ms 26060 KB Output is correct
13 Correct 2160 ms 27592 KB Output is correct
14 Correct 2516 ms 29156 KB Output is correct
15 Correct 3193 ms 33736 KB Output is correct
16 Correct 2809 ms 44652 KB Output is correct
17 Correct 3085 ms 43856 KB Output is correct