답안 #475797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475797 2021-09-24T04:48:53 Z training4usaco Regions (IOI09_regions) C++11
100 / 100
3523 ms 112832 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;
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 94672 KB Output is correct
2 Correct 44 ms 94612 KB Output is correct
3 Correct 45 ms 94608 KB Output is correct
4 Correct 51 ms 94656 KB Output is correct
5 Correct 51 ms 94552 KB Output is correct
6 Correct 63 ms 94724 KB Output is correct
7 Correct 61 ms 94712 KB Output is correct
8 Correct 84 ms 94720 KB Output is correct
9 Correct 104 ms 95156 KB Output is correct
10 Correct 131 ms 95104 KB Output is correct
11 Correct 182 ms 95336 KB Output is correct
12 Correct 168 ms 95792 KB Output is correct
13 Correct 165 ms 95412 KB Output is correct
14 Correct 306 ms 95956 KB Output is correct
15 Correct 328 ms 98376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 98604 KB Output is correct
2 Correct 1296 ms 97400 KB Output is correct
3 Correct 2145 ms 100288 KB Output is correct
4 Correct 330 ms 96064 KB Output is correct
5 Correct 503 ms 97532 KB Output is correct
6 Correct 726 ms 97016 KB Output is correct
7 Correct 1461 ms 97856 KB Output is correct
8 Correct 1157 ms 102488 KB Output is correct
9 Correct 2198 ms 102284 KB Output is correct
10 Correct 2767 ms 106904 KB Output is correct
11 Correct 3523 ms 101596 KB Output is correct
12 Correct 1210 ms 103376 KB Output is correct
13 Correct 1896 ms 103572 KB Output is correct
14 Correct 2917 ms 103188 KB Output is correct
15 Correct 2764 ms 107404 KB Output is correct
16 Correct 3409 ms 112832 KB Output is correct
17 Correct 2817 ms 111640 KB Output is correct