oj.uz

Submission #475587

# Submission time Handle Problem Language Result Execution time Memory
475587 2021-09-23T05:44:36 Z training4usaco Regions (IOI09_regions) C++11
0 / 100
 949 ms 112748 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) {
    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 Execution timed out 41 ms 94528 KB Time limit exceeded (wall clock)
2 Execution timed out 41 ms 94652 KB Time limit exceeded (wall clock)
3 Execution timed out 42 ms 94644 KB Time limit exceeded (wall clock)
4 Execution timed out 41 ms 94656 KB Time limit exceeded (wall clock)
5 Execution timed out 42 ms 94552 KB Time limit exceeded (wall clock)
6 Execution timed out 40 ms 94688 KB Time limit exceeded (wall clock)
7 Execution timed out 40 ms 94664 KB Time limit exceeded (wall clock)
8 Execution timed out 42 ms 94684 KB Time limit exceeded (wall clock)
9 Execution timed out 45 ms 95048 KB Time limit exceeded (wall clock)
10 Execution timed out 47 ms 94984 KB Time limit exceeded (wall clock)
11 Execution timed out 48 ms 95292 KB Time limit exceeded (wall clock)
12 Execution timed out 51 ms 95760 KB Time limit exceeded (wall clock)
13 Execution timed out 58 ms 95376 KB Time limit exceeded (wall clock)
14 Execution timed out 62 ms 95808 KB Time limit exceeded (wall clock)
15 Execution timed out 64 ms 98300 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 147 ms 98496 KB Time limit exceeded (wall clock)
2 Execution timed out 155 ms 97348 KB Time limit exceeded (wall clock)
3 Execution timed out 122 ms 100308 KB Time limit exceeded (wall clock)
4 Execution timed out 61 ms 95936 KB Time limit exceeded (wall clock)
5 Execution timed out 62 ms 97468 KB Time limit exceeded (wall clock)
6 Execution timed out 261 ms 96960 KB Time limit exceeded (wall clock)
7 Execution timed out 143 ms 97728 KB Time limit exceeded (wall clock)
8 Execution timed out 502 ms 102348 KB Time limit exceeded (wall clock)
9 Execution timed out 181 ms 102220 KB Time limit exceeded (wall clock)
10 Execution timed out 526 ms 106848 KB Time limit exceeded (wall clock)
11 Execution timed out 193 ms 101600 KB Time limit exceeded (wall clock)
12 Execution timed out 291 ms 103364 KB Time limit exceeded (wall clock)
13 Execution timed out 268 ms 103544 KB Time limit exceeded (wall clock)
14 Execution timed out 949 ms 103104 KB Time limit exceeded (wall clock)
15 Execution timed out 201 ms 107360 KB Time limit exceeded (wall clock)
16 Execution timed out 195 ms 112748 KB Time limit exceeded (wall clock)
17 Execution timed out 358 ms 111680 KB Time limit exceeded (wall clock)