#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, int> ii;
/* */
template<class T>
bool minimize(T &a, const T &b) {
if(a > b) {a = b; return 1;}
return 0;
}
template<class T>
bool maximize(T &a, const T &b) {
if(a < b) {a = b; return 1;}
return 0;
}
/* */
/* CODE BELOW */
const int N = 2e5 + 7, M = 1e9 + 7;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;
int n, r, q;
const int BL = 206;
class FenwickTree{
private: int n;
vector<int> bit;
public:
FenwickTree(int _n = 0):n(_n) {
bit.assign(_n + 1, 0);
}
void update(int p, int v) {
for(;p<=n;p+=p&-p) {
bit[p]+= v;
}
}
int query(int l, int r) {
int ans = 0;
for(--l;l>0;l-=l&-l) ans-= bit[l];
for(;r>0;r-=r&-r) ans+= bit[r];
return ans;
}
};
FenwickTree bit(N);
int in[N], out[N], cnt = 0;
vector<int> adj[N];
vector<int> region[N];
int cover[N];
int ans[N], type[N];
vector<ii> R1Group[N];
vector<ii> R2Group[N];
vector<ii> naiveQuery;
void dfs(int u) {
region[type[u]].pb(u);
in[u] = ++cnt;
for(int v:adj[u]) dfs(v);
out[u] = cnt;
}
int solve1(int u, int v) { // r1, r2 small
int ans = 0;
for(int x:region[v]) {
bit.update(in[x], 1);
}
for(int x:region[u]) {
ans+= bit.query(in[x], out[x]);
}
for(int x:region[v]) {
bit.update(in[x], -1);
}
return ans;
}
void solve2() { // r1 big, r2 big/small
for(int t=1;t<=r;t++) {
if(sz(region[t])>M) {
sort(all(R1Group[t]));
for(int v:region[t]) {
cover[in[v]]++;
cover[out[v]+1]--;
}
for(int i=1;i<=n;i++) {
cover[i]+= cover[i-1];
}
// process query
int u, idx;
for(int i=0;i<sz(R1Group[t]);i++) {
tie(u, idx) = R1Group[t][i];
if(i && R1Group[t][i-1].FF == u) {
ans[idx] = ans[R1Group[t][i-1].SS];
continue;
}
for(int v:region[u]) {
ans[idx]+= cover[in[v]];
}
}
for(int i=1;i<=n;i++) cover[i] = 0;
}
}
}
void solve3() { // r1 big/small, r2 big
for(int t=1;t<=r;t++) {
if(sz(region[t])>M) {
sort(all(R2Group[t]));
for(int v:region[t]) {
cover[in[v]]++;
}
for(int i=1;i<=n;i++) {
cover[i]+= cover[i-1];
}
// process query
int u, idx;
for(int i=0;i<sz(R2Group[t]);i++) {
tie(u, idx) = R2Group[t][i];
if(i && R2Group[t][i-1].FF == u) {
ans[idx] = ans[R2Group[t][i-1].SS];
continue;
}
for(int v:region[u]) {
ans[idx]+= cover[out[v]] - cover[in[v]-1];
}
}
for(int i=1;i<=n;i++) cover[i] = 0;
}
}
}
signed main() {
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//fastIO;
scanf("%d%d%d", &n, &r, &q);
int u, v; scanf("%d", &type[1]);
for(int i=2;i<=n;i++) {
scanf("%d%d", &u, &type[i]);
adj[u].pb(i);
}
dfs(1);
for(int i=1;i<=q;i++) {
scanf("%d%d", &u, &v);
if(sz(region[u])<=M&&
sz(region[v])<=M) {
ans[i] = solve1(u, v);
}
if(sz(region[u])>M) {
R1Group[u].pb(ii(v, i));
} else if(sz(region[v])>M) {
R2Group[v].pb(ii(u, i));
}
}
solve2(), solve3();
for(int i=1;i<=q;i++) {
printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d%d", &n, &r, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:170:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
170 | int u, v; scanf("%d", &type[1]);
| ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | scanf("%d%d", &u, &type[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
10 ms |
19784 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
10 ms |
19784 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
9 ms |
19784 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
9 ms |
19784 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
10 ms |
19912 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
9 ms |
19912 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
9 ms |
19912 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
10 ms |
19912 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
10 ms |
20296 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
13 ms |
20296 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
12 ms |
20552 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
14 ms |
21064 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
15 ms |
20680 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
17 ms |
21184 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
20 ms |
23752 KB |
Time limit exceeded (wall clock) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
30 ms |
24104 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
34 ms |
22920 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
34 ms |
25792 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
17 ms |
21320 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
22 ms |
22804 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
24 ms |
22352 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
33 ms |
23236 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
39 ms |
28096 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
62 ms |
27980 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
73 ms |
32708 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
78 ms |
27592 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
87 ms |
29324 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
97 ms |
29560 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
99 ms |
29100 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
78 ms |
33372 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
72 ms |
38764 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
70 ms |
37648 KB |
Time limit exceeded (wall clock) |