oj.uz

Submission #475796

# Submission time Handle Problem Language Result Execution time Memory
475796 2021-09-24T04:47:44 Z training4usaco Regions (IOI09_regions) C++11
0 / 100
 930 ms 112772 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 Execution timed out 40 ms 94656 KB Time limit exceeded (wall clock)
2 Execution timed out 41 ms 94660 KB Time limit exceeded (wall clock)
3 Execution timed out 42 ms 94604 KB Time limit exceeded (wall clock)
4 Execution timed out 48 ms 94532 KB Time limit exceeded (wall clock)
5 Execution timed out 49 ms 94632 KB Time limit exceeded (wall clock)
6 Execution timed out 40 ms 94656 KB Time limit exceeded (wall clock)
7 Execution timed out 51 ms 94668 KB Time limit exceeded (wall clock)
8 Execution timed out 45 ms 94668 KB Time limit exceeded (wall clock)
9 Execution timed out 44 ms 95016 KB Time limit exceeded (wall clock)
10 Execution timed out 51 ms 95012 KB Time limit exceeded (wall clock)
11 Execution timed out 56 ms 95296 KB Time limit exceeded (wall clock)
12 Execution timed out 61 ms 95680 KB Time limit exceeded (wall clock)
13 Execution timed out 63 ms 95296 KB Time limit exceeded (wall clock)
14 Execution timed out 69 ms 95808 KB Time limit exceeded (wall clock)
15 Execution timed out 71 ms 98308 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 168 ms 98528 KB Time limit exceeded (wall clock)
2 Execution timed out 162 ms 97344 KB Time limit exceeded (wall clock)
3 Execution timed out 133 ms 100288 KB Time limit exceeded (wall clock)
4 Execution timed out 70 ms 95996 KB Time limit exceeded (wall clock)
5 Execution timed out 69 ms 97472 KB Time limit exceeded (wall clock)
6 Execution timed out 273 ms 96936 KB Time limit exceeded (wall clock)
7 Execution timed out 157 ms 97728 KB Time limit exceeded (wall clock)
8 Execution timed out 479 ms 102464 KB Time limit exceeded (wall clock)
9 Execution timed out 163 ms 102208 KB Time limit exceeded (wall clock)
10 Execution timed out 532 ms 106776 KB Time limit exceeded (wall clock)
11 Execution timed out 202 ms 101620 KB Time limit exceeded (wall clock)
12 Execution timed out 306 ms 103352 KB Time limit exceeded (wall clock)
13 Execution timed out 231 ms 103616 KB Time limit exceeded (wall clock)
14 Execution timed out 930 ms 103092 KB Time limit exceeded (wall clock)
15 Execution timed out 214 ms 107364 KB Time limit exceeded (wall clock)
16 Execution timed out 232 ms 112772 KB Time limit exceeded (wall clock)
17 Execution timed out 386 ms 111680 KB Time limit exceeded (wall clock)