oj.uz

답안 #752873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752873 2023-06-04T07:01:11 Z chanhchuong123 Regions (IOI09_regions) C++14
0 / 100
 122 ms 28424 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] << '\n';
        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 << '\n';
        }
    }
	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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6376 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6352 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 6352 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 6736 KB Time limit exceeded (wall clock)
10 Execution timed out 8 ms 6896 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 7248 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 7760 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 7632 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 8272 KB Time limit exceeded (wall clock)
15 Execution timed out 15 ms 10320 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 35 ms 11592 KB Time limit exceeded (wall clock)
2 Execution timed out 35 ms 10832 KB Time limit exceeded (wall clock)
3 Execution timed out 35 ms 13128 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 8288 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 9552 KB Time limit exceeded (wall clock)
6 Execution timed out 30 ms 11208 KB Time limit exceeded (wall clock)
7 Execution timed out 28 ms 10900 KB Time limit exceeded (wall clock)
8 Execution timed out 41 ms 15948 KB Time limit exceeded (wall clock)
9 Execution timed out 64 ms 17480 KB Time limit exceeded (wall clock)
10 Execution timed out 70 ms 20804 KB Time limit exceeded (wall clock)
11 Execution timed out 91 ms 17572 KB Time limit exceeded (wall clock)
12 Execution timed out 112 ms 19180 KB Time limit exceeded (wall clock)
13 Execution timed out 87 ms 19144 KB Time limit exceeded (wall clock)
14 Execution timed out 122 ms 22072 KB Time limit exceeded (wall clock)
15 Execution timed out 85 ms 22588 KB Time limit exceeded (wall clock)
16 Execution timed out 98 ms 25760 KB Time limit exceeded (wall clock)
17 Execution timed out 110 ms 28424 KB Time limit exceeded (wall clock)