oj.uz

답안 #490606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490606 2021-11-28T09:56:35 Z dooompy Regions (IOI09_regions) C++11
35 / 100
 2796 ms 131076 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 i) {
    tin[i] = timer++;
    sorted[region[i]].push_back(i);

    for (auto a : adj[i]) {
        dfs(a);
    }

    tout[i] = timer - 1;
}

void genPar(int cur, int original, int cnt) {
    par[ind[original]][region[cur]] += cnt;
    cnt += (region[cur] == original);
    for (auto a : par[cur]) {
        genPar(a, original, cnt);
    }
}

int genChild(int cur, int original) {
    int current = (region[cur] == original);

    for (auto a : par[cur]) {
        current += genChild(a, original);
    }

    child[ind[original]][region[cur]] += current;
    return current;
}

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:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:61:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (l < sorted[reg1].size() || r < sorted[reg2].size()) {
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if ((l < sorted[reg1].size()) && (r == sorted[reg2].size() || tin[sorted[reg1][l]] < tin[sorted[reg2][r]])) {
      |              ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:62:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         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 39 ms 94632 KB Output is correct
2 Correct 38 ms 94676 KB Output is correct
3 Correct 40 ms 94644 KB Output is correct
4 Correct 42 ms 94644 KB Output is correct
5 Correct 45 ms 94704 KB Output is correct
6 Correct 57 ms 94768 KB Output is correct
7 Correct 67 ms 94656 KB Output is correct
8 Correct 74 ms 94788 KB Output is correct
9 Correct 84 ms 95128 KB Output is correct
10 Correct 112 ms 95040 KB Output is correct
11 Correct 143 ms 95416 KB Output is correct
12 Correct 189 ms 95796 KB Output is correct
13 Correct 193 ms 95496 KB Output is correct
14 Correct 264 ms 95980 KB Output is correct
15 Correct 287 ms 98416 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 72 ms 131076 KB Execution killed with signal 9
2 Runtime error 81 ms 131076 KB Execution killed with signal 9
3 Runtime error 85 ms 131076 KB Execution killed with signal 9
4 Correct 283 ms 95904 KB Output is correct
5 Correct 391 ms 97572 KB Output is correct
6 Runtime error 71 ms 131076 KB Execution killed with signal 9
7 Runtime error 85 ms 131076 KB Execution killed with signal 9
8 Runtime error 82 ms 131076 KB Execution killed with signal 9
9 Correct 1823 ms 102320 KB Output is correct
10 Runtime error 100 ms 131076 KB Execution killed with signal 9
11 Correct 2796 ms 101636 KB Output is correct
12 Runtime error 124 ms 131076 KB Execution killed with signal 9
13 Runtime error 112 ms 131076 KB Execution killed with signal 9
14 Runtime error 119 ms 131076 KB Execution killed with signal 9
15 Runtime error 106 ms 131076 KB Execution killed with signal 9
16 Runtime error 118 ms 131076 KB Execution killed with signal 9
17 Runtime error 104 ms 131076 KB Execution killed with signal 9