oj.uz

Submission #490617

# Submission time Handle Problem Language Result Execution time Memory
490617 2021-11-28T10:55:45 Z dooompy Regions (IOI09_regions) C++11
100 / 100
 3133 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;
}

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 94716 KB Output is correct
2 Correct 38 ms 94680 KB Output is correct
3 Correct 40 ms 94584 KB Output is correct
4 Correct 42 ms 94656 KB Output is correct
5 Correct 43 ms 94584 KB Output is correct
6 Correct 53 ms 94748 KB Output is correct
7 Correct 69 ms 94752 KB Output is correct
8 Correct 57 ms 94888 KB Output is correct
9 Correct 80 ms 95072 KB Output is correct
10 Correct 131 ms 95132 KB Output is correct
11 Correct 141 ms 95384 KB Output is correct
12 Correct 183 ms 95804 KB Output is correct
13 Correct 179 ms 95460 KB Output is correct
14 Correct 227 ms 95964 KB Output is correct
15 Correct 285 ms 98412 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 98636 KB Output is correct
2 Correct 1156 ms 97432 KB Output is correct
3 Correct 1925 ms 100332 KB Output is correct
4 Correct 264 ms 95996 KB Output is correct
5 Correct 416 ms 97564 KB Output is correct
6 Correct 662 ms 97044 KB Output is correct
7 Correct 1351 ms 97844 KB Output is correct
8 Correct 1075 ms 102648 KB Output is correct
9 Correct 1866 ms 102312 KB Output is correct
10 Correct 2482 ms 106948 KB Output is correct
11 Correct 3133 ms 101632 KB Output is correct
12 Correct 1145 ms 103364 KB Output is correct
13 Correct 1421 ms 103604 KB Output is correct
14 Correct 2053 ms 103232 KB Output is correct
15 Correct 2514 ms 107436 KB Output is correct
16 Correct 2465 ms 112864 KB Output is correct
17 Correct 2252 ms 111684 KB Output is correct