oj.uz

Submission #490620

# Submission time Handle Problem Language Result Execution time Memory
490620 2021-11-28T10:58:48 Z dooompy Regions (IOI09_regions) C++11
100 / 100
 3373 ms 112868 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;
    cnt += (region[curr] == originalReg);

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

// 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 36 ms 94664 KB Output is correct
2 Correct 37 ms 94664 KB Output is correct
3 Correct 38 ms 94608 KB Output is correct
4 Correct 41 ms 94612 KB Output is correct
5 Correct 45 ms 94652 KB Output is correct
6 Correct 57 ms 94660 KB Output is correct
7 Correct 67 ms 94644 KB Output is correct
8 Correct 64 ms 94832 KB Output is correct
9 Correct 87 ms 95144 KB Output is correct
10 Correct 124 ms 95128 KB Output is correct
11 Correct 147 ms 95328 KB Output is correct
12 Correct 185 ms 95680 KB Output is correct
13 Correct 216 ms 95364 KB Output is correct
14 Correct 276 ms 95976 KB Output is correct
15 Correct 288 ms 98412 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 98756 KB Output is correct
2 Correct 1260 ms 97436 KB Output is correct
3 Correct 1995 ms 100340 KB Output is correct
4 Correct 332 ms 96004 KB Output is correct
5 Correct 449 ms 97444 KB Output is correct
6 Correct 900 ms 97048 KB Output is correct
7 Correct 1512 ms 97848 KB Output is correct
8 Correct 1233 ms 102536 KB Output is correct
9 Correct 2144 ms 102316 KB Output is correct
10 Correct 2783 ms 106940 KB Output is correct
11 Correct 3373 ms 101632 KB Output is correct
12 Correct 1205 ms 103412 KB Output is correct
13 Correct 1472 ms 103592 KB Output is correct
14 Correct 2309 ms 103224 KB Output is correct
15 Correct 2495 ms 107436 KB Output is correct
16 Correct 2677 ms 112868 KB Output is correct
17 Correct 2284 ms 111684 KB Output is correct