#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define MAX 200010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define B 200
vector<ll> adj[MAX];
vector<ll> rr[MAX];
pll range[MAX];
ll rrr[MAX];
ll cnt = 0;
ll num[MAX];
vector<vector<ll>> tdp, bdp;
void dfs(ll x, ll p = 0) {
range[x].first = range[x].second = ++cnt;
tdp[x] = tdp[p];
if (num[rrr[x]] != -1) tdp[x][num[rrr[x]]]++, bdp[x][num[rrr[x]]]++;
for (auto v : adj[x]) {
if (v == p) continue;
dfs(v, x);
range[x].second = max(range[x].second, range[v].second);
for (ll i = 0; i < bdp[x].size(); i++) bdp[x][i] += bdp[v][i];
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll N, R, Q;
cin >> N >> R >> Q;
ll i;
ll p, r;
cin >> r;
rr[r].push_back(1);
rrr[1] = r;
for (i = 2; i <= N; i++) {
cin >> p >> r;
rrr[i] = r;
adj[p].push_back(i);
adj[i].push_back(p);
rr[r].push_back(i);
}
ll nn = 0;
for (i = 0; i <= R; i++) {
if (rr[i].size() >= B) num[i] = nn++;
else num[i] = -1;
}
tdp = vector<vector<ll>>(N + 2, vector<ll>(nn));
bdp = vector<vector<ll>>(N + 2, vector<ll>(nn));
ll a, b;
map<pll, bool> chk;
map<pll, long long> val;
dfs(1);
for (i = 1; i <= Q; i++) {
cin >> a >> b;
if (chk[{a, b}]) cout << val[{a, b}] << endl;
else {
long long ans = 0;
if (rr[a].size() < rr[b].size()) {
if (num[b] != -1) {
for (auto x : rr[a]) ans += bdp[x][num[b]];
}
else {
for (auto x : rr[a]) {
for (auto y : rr[b]) {
if (range[x].first <= range[y].first && range[y].second <= range[x].second) ans++;
}
}
}
}
else {
if (num[a] != -1) {
for (auto x : rr[b]) ans += tdp[x][num[a]];
}
else {
for (auto x : rr[a]) {
for (auto y : rr[b]) {
if (range[x].first <= range[y].first && range[y].second <= range[x].second) ans++;
}
}
}
}
chk[{a, b}] = 1;
val[{a, b}] = ans;
cout << ans << endl;
}
}
}
Compilation message
regions.cpp: In function 'void dfs(ll, ll)':
regions.cpp:31:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (ll i = 0; i < bdp[x].size(); i++) bdp[x][i] += bdp[v][i];
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9672 KB |
Output is correct |
2 |
Correct |
5 ms |
9672 KB |
Output is correct |
3 |
Correct |
10 ms |
9724 KB |
Output is correct |
4 |
Correct |
10 ms |
9672 KB |
Output is correct |
5 |
Correct |
13 ms |
9812 KB |
Output is correct |
6 |
Correct |
14 ms |
10032 KB |
Output is correct |
7 |
Correct |
44 ms |
10088 KB |
Output is correct |
8 |
Correct |
45 ms |
10284 KB |
Output is correct |
9 |
Correct |
61 ms |
11268 KB |
Output is correct |
10 |
Correct |
95 ms |
11632 KB |
Output is correct |
11 |
Correct |
151 ms |
12352 KB |
Output is correct |
12 |
Correct |
206 ms |
13528 KB |
Output is correct |
13 |
Correct |
283 ms |
13664 KB |
Output is correct |
14 |
Correct |
623 ms |
14232 KB |
Output is correct |
15 |
Correct |
616 ms |
21692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1308 ms |
82740 KB |
Output is correct |
2 |
Correct |
1156 ms |
126336 KB |
Output is correct |
3 |
Runtime error |
84 ms |
131076 KB |
Execution killed with signal 9 |
4 |
Correct |
291 ms |
15940 KB |
Output is correct |
5 |
Correct |
397 ms |
20028 KB |
Output is correct |
6 |
Correct |
581 ms |
45416 KB |
Output is correct |
7 |
Correct |
907 ms |
54644 KB |
Output is correct |
8 |
Correct |
1184 ms |
115580 KB |
Output is correct |
9 |
Runtime error |
93 ms |
131076 KB |
Execution killed with signal 9 |
10 |
Runtime error |
108 ms |
131076 KB |
Execution killed with signal 9 |
11 |
Runtime error |
126 ms |
131076 KB |
Execution killed with signal 9 |
12 |
Runtime error |
102 ms |
131076 KB |
Execution killed with signal 9 |
13 |
Runtime error |
119 ms |
131076 KB |
Execution killed with signal 9 |
14 |
Correct |
4304 ms |
103392 KB |
Output is correct |
15 |
Execution timed out |
8053 ms |
67524 KB |
Time limit exceeded |
16 |
Runtime error |
110 ms |
131076 KB |
Execution killed with signal 9 |
17 |
Correct |
5815 ms |
123724 KB |
Output is correct |