oj.uz

답안 #752874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752874 2023-06-04T07:08:09 Z chanhchuong123 Regions (IOI09_regions) C++14
100 / 100
 2864 ms 28368 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define MASK(i) (1 << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};

const int MAXR = 25005;
const int MAX = 200005;
const int C = 500;
int n, R, q;
vector<int> adj[MAX];
vector<int> node[MAXR];
vector<pair<int, int>> queries[MAXR];

int timer;
int st[MAX];
int en[MAX];
int cntLarge;
int idLarge[MAXR];
void dfs(int u) {
    st[u] = timer++;
    for (int v: adj[u]) dfs(v);
    en[u] = timer - 1;
}
int pre[MAX];
long long ansLarge[C][MAXR];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    cin >> n >> R >> q;
    int r1;  cin >> r1;
    node[--r1].push_back(0);
    for (int i = 1; i < n; ++i) {
        int p, r; cin >> p >> r;
        node[--r].push_back(i);
        adj[--p].push_back(i);
    }
    dfs(0);
    memset(idLarge, -1, sizeof idLarge);
    for (int i = 0; i < R; ++i) {
        sort(all(node[i]), [](const int &u, const int &v) {
            return st[u] < st[v];
        });
        if (node[i].size() >= C) {
            idLarge[i] = cntLarge++;
            memset(pre, 0, sizeof pre);
            for (int j: node[i]) ++pre[st[j] + 1], --pre[en[j] + 1];
            for (int j = 1; j < n; ++j) pre[j] += pre[j - 1];
            for (int k = 0; k < R; ++k) {
                for (int j: node[k]) ansLarge[idLarge[i]][k] += pre[st[j]];
            }
        } else {
            for (int j: node[i]) {
                queries[i].push_back({st[j], -1});
                queries[i].push_back({en[j], +1});
            }
            sort(all(queries[i]));
        }
    }
    while (q--) {
        int r1, r2; cin >> r1 >> r2; --r1; --r2;
        if (idLarge[r1] != -1) cout << ansLarge[idLarge[r1]][r2] << endl;
        else {
            long long answer = 0;
            for (int i = 0, j = -1; i < queries[r1].size(); ++i) {
                while (j + 1 < node[r2].size() && st[node[r2][j + 1]] <= queries[r1][i].fi) ++j;
                answer += queries[r1][i].se * (j + 1);
            }
            cout << answer << endl;
        }
    }
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:88:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for (int i = 0, j = -1; i < queries[r1].size(); ++i) {
      |                                     ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 while (j + 1 < node[r2].size() && st[node[r2][j + 1]] <= queries[r1][i].fi) ++j;
      |                        ~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:50:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6224 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 4 ms 6224 KB Output is correct
4 Correct 9 ms 6224 KB Output is correct
5 Correct 12 ms 6224 KB Output is correct
6 Correct 11 ms 6352 KB Output is correct
7 Correct 29 ms 6352 KB Output is correct
8 Correct 32 ms 6352 KB Output is correct
9 Correct 48 ms 6736 KB Output is correct
10 Correct 77 ms 6864 KB Output is correct
11 Correct 92 ms 7236 KB Output is correct
12 Correct 119 ms 7760 KB Output is correct
13 Correct 156 ms 7632 KB Output is correct
14 Correct 177 ms 8340 KB Output is correct
15 Correct 215 ms 10336 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1002 ms 11612 KB Output is correct
2 Correct 1344 ms 10740 KB Output is correct
3 Correct 1794 ms 13204 KB Output is correct
4 Correct 291 ms 8272 KB Output is correct
5 Correct 349 ms 9552 KB Output is correct
6 Correct 567 ms 11216 KB Output is correct
7 Correct 1016 ms 10832 KB Output is correct
8 Correct 794 ms 15944 KB Output is correct
9 Correct 1489 ms 17484 KB Output is correct
10 Correct 2288 ms 20680 KB Output is correct
11 Correct 2094 ms 17456 KB Output is correct
12 Correct 1249 ms 19252 KB Output is correct
13 Correct 1662 ms 19188 KB Output is correct
14 Correct 2044 ms 22180 KB Output is correct
15 Correct 2190 ms 22600 KB Output is correct
16 Correct 2864 ms 25756 KB Output is correct
17 Correct 2479 ms 28368 KB Output is correct