oj.uz

Submission #475794

# Submission time Handle Problem Language Result Execution time Memory
475794 2021-09-24T04:47:09 Z training4usaco Regions (IOI09_regions) C++11
0 / 100
 246 ms 112876 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 Incorrect 41 ms 94596 KB Expected integer, but "1:" found
2 Incorrect 39 ms 94660 KB Expected integer, but "1:" found
3 Incorrect 43 ms 94708 KB Expected integer, but "1:" found
4 Incorrect 42 ms 94548 KB Expected integer, but "1:" found
5 Runtime error 41 ms 94592 KB Execution killed with signal 13
6 Incorrect 40 ms 94744 KB Expected integer, but "1:" found
7 Runtime error 49 ms 94656 KB Execution killed with signal 13
8 Runtime error 40 ms 94664 KB Execution killed with signal 13
9 Runtime error 41 ms 95040 KB Execution killed with signal 13
10 Runtime error 46 ms 95048 KB Execution killed with signal 13
11 Runtime error 50 ms 95392 KB Execution killed with signal 13
12 Runtime error 56 ms 95792 KB Execution killed with signal 13
13 Runtime error 55 ms 95316 KB Execution killed with signal 13
14 Runtime error 72 ms 95888 KB Execution killed with signal 13
15 Runtime error 66 ms 98268 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 98504 KB Execution killed with signal 13
2 Runtime error 103 ms 97368 KB Execution killed with signal 13
3 Runtime error 103 ms 100296 KB Execution killed with signal 13
4 Runtime error 69 ms 95852 KB Execution killed with signal 13
5 Runtime error 72 ms 97520 KB Execution killed with signal 13
6 Runtime error 93 ms 97004 KB Execution killed with signal 13
7 Runtime error 107 ms 97696 KB Execution killed with signal 13
8 Runtime error 127 ms 102452 KB Execution killed with signal 13
9 Runtime error 175 ms 102280 KB Execution killed with signal 13
10 Runtime error 212 ms 106812 KB Execution killed with signal 13
11 Runtime error 214 ms 101576 KB Execution killed with signal 13
12 Runtime error 246 ms 103312 KB Execution killed with signal 13
13 Runtime error 236 ms 103540 KB Execution killed with signal 13
14 Runtime error 203 ms 103196 KB Execution killed with signal 13
15 Runtime error 191 ms 107344 KB Execution killed with signal 13
16 Runtime error 190 ms 112876 KB Execution killed with signal 13
17 Runtime error 193 ms 111648 KB Execution killed with signal 13