oj.uz

답안 #490612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490612 2021-11-28T10:49:04 Z dooompy Regions (IOI09_regions) C++11
100 / 100
 3348 ms 112960 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

#define MAXN 200005
#define MAXR 25005
#define INF (long long)1e18
#define BLOCK 450

int n, r, q;
vector<int> region(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 dfs(int curr) {
    // cout << "curr: " << curr << endl;
    tin[curr] = timer++;
    sorted[region[curr]].push_back(curr);

    for (auto next: adj[curr]) {
        dfs(next);
    }
    tout[curr] = timer - 1;
}
// Get answer for (a, b), sz[a] > BLOCK, sz[b] <= BLOCK
void genPar(int curr, int originalReg, int cnt) {
    par[ind[originalReg]][region[curr]] += cnt;
    int newCount = cnt + (region[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 = (region[curr] == originalReg);

    for(auto child : adj[curr]) {
        sub += genChild(child, originalReg);
    }

    child[ind[originalReg]][region[curr]] += sub;
    return sub;
}

bool isAnc(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int getAns(int reg1, int reg2) {
    int l = 0, r = 0;
    int ans = 0;
    stack<int> st;

    while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
        if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
            while (!st.empty() && !isAnc(st.top(), sorted[reg1][l])) {
                st.pop();
            }

            st.push(sorted[reg1][l]);
            l++;
        } else {
            while (!st.empty() && !isAnc(st.top(), sorted[reg2][r])) {
                st.pop();
            }

            ans += st.size();
            r++;
        }
    }

    return ans;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, r, q; cin >> n >> r >> q;
    cin >> region[1];

    for (int i = 2; i <= n; i++) {
        int s; cin >> s >> region[i];
        adj[s].push_back(i);
    }

    dfs(1);

    int idx = 0;

    for (int i = 1; i <= r; i++) {
        if (sorted[i].size() > BLOCK) {
            largeRegions.push_back(i);
            ind[i] = idx++;
        }
    }

    for (auto a : largeRegions) {
        genPar(1, a, 0);
        genChild(1, a);
    }

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;

        if (sorted[a].size() <= BLOCK && sorted[b].size() <= BLOCK) {
            cout << getAns(a, b) << 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:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:65:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |              ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:66:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |                                           ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 94656 KB Output is correct
2 Correct 42 ms 94676 KB Output is correct
3 Correct 41 ms 94600 KB Output is correct
4 Correct 46 ms 94624 KB Output is correct
5 Correct 46 ms 94664 KB Output is correct
6 Correct 58 ms 94752 KB Output is correct
7 Correct 63 ms 94668 KB Output is correct
8 Correct 65 ms 94660 KB Output is correct
9 Correct 87 ms 95096 KB Output is correct
10 Correct 127 ms 95124 KB Output is correct
11 Correct 163 ms 95296 KB Output is correct
12 Correct 205 ms 95804 KB Output is correct
13 Correct 191 ms 95448 KB Output is correct
14 Correct 269 ms 95976 KB Output is correct
15 Correct 243 ms 98412 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1111 ms 98636 KB Output is correct
2 Correct 1241 ms 97440 KB Output is correct
3 Correct 1991 ms 100344 KB Output is correct
4 Correct 288 ms 96000 KB Output is correct
5 Correct 347 ms 97564 KB Output is correct
6 Correct 763 ms 97044 KB Output is correct
7 Correct 1420 ms 97844 KB Output is correct
8 Correct 1047 ms 102636 KB Output is correct
9 Correct 1762 ms 102312 KB Output is correct
10 Correct 2503 ms 106944 KB Output is correct
11 Correct 3348 ms 101636 KB Output is correct
12 Correct 1038 ms 103412 KB Output is correct
13 Correct 1590 ms 103728 KB Output is correct
14 Correct 2124 ms 103216 KB Output is correct
15 Correct 2309 ms 107432 KB Output is correct
16 Correct 2596 ms 112960 KB Output is correct
17 Correct 2416 ms 111684 KB Output is correct