oj.uz

답안 #738958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
738958 2023-05-09T17:34:59 Z lorenzoferrari Regions (IOI09_regions) C++17
0 / 100
 13 ms 12584 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
using LL = long long;

static constexpr int N = 200000;
static constexpr int R = 25000;
static constexpr int SQ = 700;

static int h[N], p[N], f[R], in[N], out[N];
static vector<int> fi(R, -1), ff;
static vector<int> adj[N];
static vector<array<int, 2>> ev[R];
static vector<array<int, 2>> vs[R];
vector<vector<LL>> sub, anc;

int t = 0;
static void dfs0(int v) {
    in[v] = t++;
    for (int u : adj[v]) {
        dfs0(u);
    }
    out[v] = t;
}

static int dfs1(int v, const int i, int acc = 0) {
    int cnt = 0;
    for (int u : adj[v]) {
        cnt += dfs1(u, i, acc + (h[v] == ff[i]));
    }
    sub[h[v]][i] += cnt;
    anc[h[v]][i] += acc;
    return cnt + (h[v] == ff[i]);
}

int main() {
#ifdef EVAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n; cin >> n;
    int r; cin >> r;
    int q; cin >> q;
    cin >> h[0]; ++f[--h[0]];
    for (int i = 1; i < n; ++i) {
        cin >> p[i] >> h[i];
        --p[i], --h[i];
        adj[p[i]].push_back(i);
        ++f[h[i]];
    }
    for (int i = 0; i < r; ++i) {
        if (f[i] >= SQ) {
            fi[i] = ff.size();
            ff.push_back(i);
        }
    }

    dfs0(0);

    for (int v = 0; v < n; ++v) {
        vs[h[v]].push_back({in[v], v});
        ev[h[v]].push_back({in[v], +1});
        ev[h[v]].push_back({out[v],-1});
    }
    for (int i = 0; i < r; ++i) {
        sort(begin(ev[i]), end(ev[i]));
        sort(begin(vs[i]), end(vs[i]));
    }

    sub.assign(r, vector<LL>(ff.size()));
    anc.assign(r, vector<LL>(ff.size()));
    for (int i = 0; i < (int)ff.size(); ++i) {
        dfs1(0, i);
    }

    for (int r1, r2; q--;) {
        cin >> r1 >> r2;
        --r1, --r2;
        if (f[r2] >= SQ) {
            cout << sub[r1][fi[r2]] << endl;
        } else if (f[r1] >= SQ) {
            cout << anc[r2][fi[r1]] << endl;
        } else {
            LL ans = 0;
            int j = 0, act = 0;
            for (auto [tin, v] : vs[r2]) {
                while (j != (int)ev[r1].size() && ev[r1][j][0] <= tin) {
                    act += ev[r1][j][1];
                    ++j;
                }
                ans += act;
            }
            cout << ans << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 12460 KB Execution killed with signal 11
2 Runtime error 9 ms 12496 KB Execution killed with signal 11
3 Runtime error 9 ms 12460 KB Execution killed with signal 11
4 Runtime error 10 ms 12496 KB Execution killed with signal 11
5 Runtime error 10 ms 12560 KB Execution killed with signal 11
6 Runtime error 9 ms 12496 KB Execution killed with signal 11
7 Runtime error 10 ms 12444 KB Execution killed with signal 11
8 Runtime error 13 ms 12484 KB Execution killed with signal 11
9 Runtime error 10 ms 12496 KB Execution killed with signal 11
10 Runtime error 12 ms 12484 KB Execution killed with signal 11
11 Runtime error 9 ms 12496 KB Execution killed with signal 11
12 Runtime error 12 ms 12508 KB Execution killed with signal 11
13 Runtime error 10 ms 12584 KB Execution killed with signal 11
14 Runtime error 10 ms 12496 KB Execution killed with signal 11
15 Runtime error 12 ms 12516 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 12496 KB Execution killed with signal 11
2 Runtime error 9 ms 12496 KB Execution killed with signal 11
3 Runtime error 9 ms 12536 KB Execution killed with signal 11
4 Runtime error 11 ms 12516 KB Execution killed with signal 11
5 Runtime error 9 ms 12496 KB Execution killed with signal 11
6 Runtime error 9 ms 12496 KB Execution killed with signal 11
7 Runtime error 8 ms 12496 KB Execution killed with signal 11
8 Runtime error 10 ms 12460 KB Execution killed with signal 11
9 Runtime error 9 ms 12496 KB Execution killed with signal 11
10 Runtime error 9 ms 12532 KB Execution killed with signal 11
11 Runtime error 9 ms 12496 KB Execution killed with signal 11
12 Runtime error 12 ms 12540 KB Execution killed with signal 11
13 Runtime error 9 ms 12468 KB Execution killed with signal 11
14 Runtime error 10 ms 12536 KB Execution killed with signal 11
15 Runtime error 11 ms 12496 KB Execution killed with signal 11
16 Runtime error 10 ms 12528 KB Execution killed with signal 11
17 Runtime error 10 ms 12496 KB Execution killed with signal 11