Submission #490624

# Submission time Handle Problem Language Result Execution time Memory
490624 2021-11-28T11:04:45 Z dooompy Regions (IOI09_regions) C++11
35 / 100
2847 ms 131076 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);
//    }
//}

void genPar(int cur, int original, int cnt) {
    par[ind[original]][region[cur]] += cnt;
    int newcount = cnt + (region[cur] == original);
    for (auto a : par[cur]) {
        genPar(a, original, 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:72:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:72:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |              ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:73:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |                                           ~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 38 ms 94656 KB Output is correct
2 Correct 39 ms 94656 KB Output is correct
3 Correct 41 ms 94664 KB Output is correct
4 Correct 42 ms 94632 KB Output is correct
5 Correct 45 ms 94684 KB Output is correct
6 Correct 57 ms 94756 KB Output is correct
7 Correct 70 ms 94748 KB Output is correct
8 Correct 93 ms 94744 KB Output is correct
9 Correct 86 ms 95176 KB Output is correct
10 Correct 105 ms 95044 KB Output is correct
11 Correct 160 ms 95288 KB Output is correct
12 Correct 190 ms 95912 KB Output is correct
13 Correct 176 ms 95416 KB Output is correct
14 Correct 260 ms 96064 KB Output is correct
15 Correct 320 ms 98368 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 131076 KB Execution killed with signal 9
2 Runtime error 87 ms 131076 KB Execution killed with signal 9
3 Runtime error 76 ms 131076 KB Execution killed with signal 9
4 Correct 282 ms 96064 KB Output is correct
5 Correct 390 ms 97456 KB Output is correct
6 Runtime error 76 ms 131076 KB Execution killed with signal 9
7 Runtime error 84 ms 131076 KB Execution killed with signal 9
8 Runtime error 82 ms 131076 KB Execution killed with signal 9
9 Correct 1959 ms 102320 KB Output is correct
10 Runtime error 99 ms 131076 KB Execution killed with signal 9
11 Correct 2847 ms 101632 KB Output is correct
12 Runtime error 138 ms 131076 KB Execution killed with signal 9
13 Runtime error 111 ms 131076 KB Execution killed with signal 9
14 Runtime error 124 ms 131076 KB Execution killed with signal 9
15 Runtime error 117 ms 131076 KB Execution killed with signal 9
16 Runtime error 107 ms 131076 KB Execution killed with signal 9
17 Runtime error 105 ms 131076 KB Execution killed with signal 9