oj.uz

Submission #490613

# Submission time Handle Problem Language Result Execution time Memory
490613 2021-11-28T10:51:04 Z dooompy Regions (IOI09_regions) C++11
100 / 100
 2875 ms 112864 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

#define MAXN 200005
#define MAXR 25005
#define INF (long long)1e18
#define BLOCK 450

int n, r, q;
vector<int> region(MAXN);
vector<vector<int>> adj(MAXN);
int timer = 1;
int tin[MAXN], tout[MAXN];
vector<vector<int>> sorted(MAXR); // sorted[r] stores the nodes from region r in sorted order of {tin, tout}
vector<int> ind(MAXR);
vector<vector<int>> par(BLOCK, vector<int>(MAXR));
vector<vector<int>> child(BLOCK, vector<int>(MAXR));
vector<int> largeRegions;

void dfs(int i) {
    tin[i] = timer++;
    sorted[region[i]].push_back(i);

    for (auto a : adj[i]) {
        dfs(a);
    }

    tout[i] = timer - 1;
}
// Get answer for (a, b), sz[a] > BLOCK, sz[b] <= BLOCK
void genPar(int curr, int originalReg, int cnt) {
    par[ind[originalReg]][region[curr]] += cnt;
    int newCount = cnt + (region[curr] == originalReg);

    for(auto child : adj[curr]) {
        genPar(child, originalReg, newCount);
    }
}

// Get answer for (a, b), sz[a] <= BLOCK, sz[b] > BLOCK

int genChild(int curr, int originalReg) {
    int sub = (region[curr] == originalReg);

    for(auto child : adj[curr]) {
        sub += genChild(child, originalReg);
    }

    child[ind[originalReg]][region[curr]] += sub;
    return sub;
}

bool isAnc(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int getAns(int reg1, int reg2) {
    int l = 0, r = 0;
    int ans = 0;
    stack<int> st;

    while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
        if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
            while (!st.empty() && !isAnc(st.top(), sorted[reg1][l])) {
                st.pop();
            }

            st.push(sorted[reg1][l]);
            l++;
        } else {
            while (!st.empty() && !isAnc(st.top(), sorted[reg2][r])) {
                st.pop();
            }

            ans += st.size();
            r++;
        }
    }

    return ans;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, r, q; cin >> n >> r >> q;
    cin >> region[1];

    for (int i = 2; i <= n; i++) {
        int s; cin >> s >> region[i];
        adj[s].push_back(i);
    }

    dfs(1);

    int idx = 0;

    for (int i = 1; i <= r; i++) {
        if (sorted[i].size() > BLOCK) {
            largeRegions.push_back(i);
            ind[i] = idx++;
        }
    }

    for (auto a : largeRegions) {
        genPar(1, a, 0);
        genChild(1, a);
    }

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;

        if (sorted[a].size() <= BLOCK && sorted[b].size() <= BLOCK) {
            cout << getAns(a, b) << endl;
            continue;
        }

        if (sorted[a].size() > BLOCK) {
            cout << par[ind[a]][b] << endl;
        } else {
            cout << child[ind[b]][a] << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int getAns(int, int)':
regions.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:65:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |              ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:66:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |                                           ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94576 KB Output is correct
2 Correct 38 ms 94676 KB Output is correct
3 Correct 40 ms 94556 KB Output is correct
4 Correct 40 ms 94692 KB Output is correct
5 Correct 47 ms 94608 KB Output is correct
6 Correct 59 ms 94688 KB Output is correct
7 Correct 69 ms 94680 KB Output is correct
8 Correct 73 ms 94784 KB Output is correct
9 Correct 89 ms 95152 KB Output is correct
10 Correct 125 ms 95064 KB Output is correct
11 Correct 181 ms 95380 KB Output is correct
12 Correct 185 ms 95704 KB Output is correct
13 Correct 213 ms 95444 KB Output is correct
14 Correct 224 ms 95976 KB Output is correct
15 Correct 295 ms 98412 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 98636 KB Output is correct
2 Correct 1202 ms 97456 KB Output is correct
3 Correct 2068 ms 100340 KB Output is correct
4 Correct 289 ms 96016 KB Output is correct
5 Correct 394 ms 97564 KB Output is correct
6 Correct 802 ms 97044 KB Output is correct
7 Correct 1342 ms 97844 KB Output is correct
8 Correct 1321 ms 102528 KB Output is correct
9 Correct 2013 ms 102320 KB Output is correct
10 Correct 2674 ms 106944 KB Output is correct
11 Correct 2875 ms 101648 KB Output is correct
12 Correct 1271 ms 103376 KB Output is correct
13 Correct 1714 ms 103528 KB Output is correct
14 Correct 2361 ms 103232 KB Output is correct
15 Correct 2718 ms 107456 KB Output is correct
16 Correct 2567 ms 112864 KB Output is correct
17 Correct 2493 ms 111680 KB Output is correct