#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 70
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[rrr[b]] != -1) {
for (auto x : rr[a]) ans += bdp[x][num[rrr[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[rrr[a]] != -1) {
for (auto x : rr[b]) ans += tdp[x][num[rrr[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];
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9672 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9672 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9800 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9740 KB |
Output is correct |
| 5 |
Correct |
14 ms |
9840 KB |
Output is correct |
| 6 |
Correct |
25 ms |
10060 KB |
Output is correct |
| 7 |
Correct |
38 ms |
10172 KB |
Output is correct |
| 8 |
Correct |
44 ms |
10304 KB |
Output is correct |
| 9 |
Correct |
62 ms |
11256 KB |
Output is correct |
| 10 |
Correct |
88 ms |
11580 KB |
Output is correct |
| 11 |
Incorrect |
176 ms |
13680 KB |
Output isn't correct |
| 12 |
Incorrect |
186 ms |
14860 KB |
Output isn't correct |
| 13 |
Incorrect |
218 ms |
50500 KB |
Output isn't correct |
| 14 |
Incorrect |
256 ms |
62124 KB |
Output isn't correct |
| 15 |
Incorrect |
303 ms |
95628 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
78 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Incorrect |
1171 ms |
126212 KB |
Output isn't correct |
| 3 |
Runtime error |
82 ms |
131076 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
357 ms |
40400 KB |
Output isn't correct |
| 5 |
Incorrect |
406 ms |
50096 KB |
Output isn't correct |
| 6 |
Incorrect |
649 ms |
45448 KB |
Output isn't correct |
| 7 |
Incorrect |
750 ms |
83080 KB |
Output isn't correct |
| 8 |
Runtime error |
76 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
94 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
110 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
126 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
107 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
109 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
111 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
109 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
126 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
115 ms |
131076 KB |
Execution killed with signal 9 |
