oj.uz

Submission #475585

# Submission time Handle Problem Language Result Execution time Memory
475585 2021-09-23T05:40:07 Z training4usaco Regions (IOI09_regions) C++11
0 / 100
 73 ms 131076 KB 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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

int n, r, q;
vector<int> homereg(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 euler(int curr) {
    tin[curr] = timer++; 
    sorted[homereg[curr]].push_back(curr);

    for(auto next : adj[curr]) {
        euler(next);
    }
    tout[curr] = timer - 1;
}
bool isAnc(int a, int b) { 
    return tin[a] <= tin[b] && tout[b] <= tout[a]; 
}
 
// Get answer for (a, b), sz[a] > BLOCK, sz[b] <= BLOCK
void genPar(int curr, int originalReg, int cnt) {
    par[ind[originalReg]][homereg[curr]] += cnt; 
    int newCount = cnt + (homereg[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 = (homereg[curr] == originalReg); 
    
    for(auto child : adj[curr]) {
        sub += genChild(child, originalReg);
    }

    child[ind[originalReg]][homereg[curr]] += sub; 
    return sub;
}
 
// Get answer for (a, b), sz[a], sz[b] <= BLOCK
int getAns(int a, int b) {
    int l = 0;
    int r = 0; 
    int ans = 0; 
    stack<int> anc;


    while (l < sorted[a].size() || r < sorted[b].size()) {
        // cout << "l, r: " << l << " " << r << endl;
        if (l < sorted[a].size() && (r == sorted[b].size() || tin[sorted[a][l]] < tin[sorted[b][r]])) {
            // cout << "a" << endl;
            while (!anc.empty() && !isAnc(anc.top(), sorted[a][l])) {
                anc.pop(); 
            }
            anc.push(sorted[a][l]); 
            ++l;
        }
        else { 
            // cout << "b" << endl;
            while (!anc.empty() && !isAnc(anc.top(), sorted[b][r])) {
                anc.pop(); 
            }
            ans += anc.size(); 
            r++; 
        }
    }
    return ans;
}
 
int main() { 
    cin >> n >> r >> q >> homereg[1];   //  homereg[i] = employee i's home region
    for(int i = 2; i <= n; ++i) {
        int a;
        cin >> a >> homereg[i];

        adj[a].push_back(i);
    }

    euler(1);

    // for(int i = 0; i < n; ++i) {
    //     cout << tin[i] << " " << tout[i] << endl;
    // }

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

    for(auto region : largeRegions) {
        genPar(1, region, 0);
        genChild(1, region);
    }
 
    for(int i = 0; i < q; ++i) {
        int a, b; 
        cin >> a >> b;

        if (sorted[a].size() <= BLOCK && sorted[b].size() <= BLOCK) {   // brute force because lower than bounds
            cout << getAns(a, b) << endl; 
            // cout << "hello" << 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:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while (l < sorted[a].size() || r < sorted[b].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~
regions.cpp:66:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while (l < sorted[a].size() || r < sorted[b].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~~
regions.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (l < sorted[a].size() && (r == sorted[b].size() || tin[sorted[a][l]] < tin[sorted[b][r]])) {
      |             ~~^~~~~~~~~~~~~~~~~~
regions.cpp:68:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (l < sorted[a].size() && (r == sorted[b].size() || tin[sorted[a][l]] < tin[sorted[b][r]])) {
      |                                      ~~^~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:103:9: warning: unused variable 'cnt' [-Wunused-variable]
  103 |     int cnt = 0;
      |         ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 131076 KB Execution killed with signal 9
2 Runtime error 62 ms 131076 KB Execution killed with signal 9
3 Runtime error 54 ms 131076 KB Execution killed with signal 9
4 Runtime error 59 ms 131076 KB Execution killed with signal 9
5 Runtime error 60 ms 131076 KB Execution killed with signal 9
6 Runtime error 57 ms 131076 KB Execution killed with signal 9
7 Runtime error 57 ms 131076 KB Execution killed with signal 9
8 Runtime error 71 ms 131076 KB Execution killed with signal 9
9 Runtime error 57 ms 131076 KB Execution killed with signal 9
10 Runtime error 56 ms 131076 KB Execution killed with signal 9
11 Runtime error 57 ms 131076 KB Execution killed with signal 9
12 Runtime error 65 ms 131076 KB Execution killed with signal 9
13 Runtime error 54 ms 131076 KB Execution killed with signal 9
14 Runtime error 57 ms 131076 KB Execution killed with signal 9
15 Runtime error 61 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 131076 KB Execution killed with signal 9
2 Runtime error 57 ms 131076 KB Execution killed with signal 9
3 Runtime error 73 ms 131076 KB Execution killed with signal 9
4 Runtime error 55 ms 131076 KB Execution killed with signal 9
5 Runtime error 57 ms 131076 KB Execution killed with signal 9
6 Runtime error 56 ms 131076 KB Execution killed with signal 9
7 Runtime error 59 ms 131076 KB Execution killed with signal 9
8 Runtime error 54 ms 131076 KB Execution killed with signal 9
9 Runtime error 56 ms 131076 KB Execution killed with signal 9
10 Runtime error 70 ms 131076 KB Execution killed with signal 9
11 Runtime error 57 ms 131076 KB Execution killed with signal 9
12 Runtime error 59 ms 131076 KB Execution killed with signal 9
13 Runtime error 63 ms 131076 KB Execution killed with signal 9
14 Runtime error 60 ms 131076 KB Execution killed with signal 9
15 Runtime error 62 ms 131076 KB Execution killed with signal 9
16 Runtime error 61 ms 131076 KB Execution killed with signal 9
17 Runtime error 56 ms 131076 KB Execution killed with signal 9