oj.uz

Submission #475793

# Submission time Handle Problem Language Result Execution time Memory
475793 2021-09-24T04:46:12 Z training4usaco Regions (IOI09_regions) C++11
0 / 100
 215 ms 112776 KB 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

#define MAXN 200005
#define MAXR 25005
#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) {
    // cout << "curr: " << curr << endl;
    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 = 1; i <= n; ++i) {
        cout << i << ": " << 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:67:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while (l < sorted[a].size() || r < sorted[b].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~
regions.cpp:67:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while (l < sorted[a].size() || r < sorted[b].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~~
regions.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if (l < sorted[a].size() && (r == sorted[b].size() || tin[sorted[a][l]] < tin[sorted[b][r]])) {
      |             ~~^~~~~~~~~~~~~~~~~~
regions.cpp:69:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         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:105:9: warning: unused variable 'cnt' [-Wunused-variable]
  105 |     int cnt = 0;
      |         ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 94656 KB Execution killed with signal 13
2 Runtime error 45 ms 94668 KB Execution killed with signal 13
3 Runtime error 39 ms 94584 KB Execution killed with signal 13
4 Runtime error 39 ms 94612 KB Execution killed with signal 13
5 Runtime error 39 ms 94656 KB Execution killed with signal 13
6 Runtime error 41 ms 94616 KB Execution killed with signal 13
7 Runtime error 43 ms 94644 KB Execution killed with signal 13
8 Runtime error 39 ms 94692 KB Execution killed with signal 13
9 Runtime error 46 ms 95192 KB Execution killed with signal 13
10 Runtime error 47 ms 95056 KB Execution killed with signal 13
11 Runtime error 49 ms 95296 KB Execution killed with signal 13
12 Runtime error 51 ms 95756 KB Execution killed with signal 13
13 Runtime error 53 ms 95396 KB Execution killed with signal 13
14 Runtime error 58 ms 95936 KB Execution killed with signal 13
15 Runtime error 68 ms 98368 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 98496 KB Execution killed with signal 13
2 Runtime error 98 ms 97444 KB Execution killed with signal 13
3 Runtime error 94 ms 100248 KB Execution killed with signal 13
4 Runtime error 65 ms 95900 KB Execution killed with signal 13
5 Runtime error 65 ms 97532 KB Execution killed with signal 13
6 Runtime error 87 ms 96960 KB Execution killed with signal 13
7 Runtime error 88 ms 97812 KB Execution killed with signal 13
8 Runtime error 104 ms 102464 KB Execution killed with signal 13
9 Runtime error 158 ms 102168 KB Execution killed with signal 13
10 Runtime error 165 ms 106848 KB Execution killed with signal 13
11 Runtime error 215 ms 101524 KB Execution killed with signal 13
12 Runtime error 188 ms 103280 KB Execution killed with signal 13
13 Runtime error 180 ms 103552 KB Execution killed with signal 13
14 Runtime error 210 ms 103164 KB Execution killed with signal 13
15 Runtime error 181 ms 107328 KB Execution killed with signal 13
16 Runtime error 204 ms 112776 KB Execution killed with signal 13
17 Runtime error 185 ms 111552 KB Execution killed with signal 13