// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define f first
#define s second
#define pb push_back
#define inf ~((long long)1<<63)
using namespace std;
const int mod = 1000000007;
void setio(string name = "") {
ios::sync_with_stdio(false), cin.tie(nullptr);
if(name.length()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
class BIT {
private:
int size;
vector<int> bit;
vector<int> arr;
public:
BIT(int size) : size(size), bit(size + 1), arr(size) {}
void set(int ind, int val) { add(ind, val - arr[ind]); }
void add(int ind, int val) {
arr[ind] += val;
ind++;
for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
}
int prev(int ind) {
ind++;
int total = 0;
for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
return total;
}
int sum(int a, int b){
return prev(b)-(a == 0 ? 0:prev(a-1));
}
};
int N, R, timer = 0;
vector<vector<int>> cnt;
vector<int> big;
vector<vector<int>> precomp;
vector<int> st, en;
vector<vector<int>> g;
vector<vector<int>> above;
vector<int> ans;
vector<int> nums;
vector<BIT> sums;
void dfs(int s, vector<int> curr, vector<stack<int>> last){
ans[s] = ++curr[nums[s]];
if(big[nums[s]]+1) last[big[nums[s]]].push(s);
else for(int i = 0; i<last.size(); i++) above[s][i] = last[i].empty() ? -1:last[i].top();
st[s] = timer++;
for(int i: g[s]) dfs(i, curr, last);
if(big[nums[s]]+1) last[big[nums[s]]].pop();
curr[nums[s]]--;
en[s] = timer-1;
}
void getComp(int size){
precomp.resize(size, vector<int>(size, 0));
vector<int> b(size);
for(int i = R-1; i>=0; i--) if(big[i]+1) b[--size] = i;
for(int i = 0; i<b.size(); i++){
for(int j: cnt[b[i]])
sums[i].set(st[j], 1);
for(int j = 0; j<b.size(); j++) for(int k: cnt[b[j]])
precomp[j][i]+=sums[i].sum(st[k], en[k])-(j == i ? 1:0);
}
}
int main() {
setio();
int Q; cin >> N >> R >> Q;
g.resize(N, vector<int>(0));
nums.resize(N);
cin >> nums[0];
for(int i = 1; i<N; i++){
int par; cin >> par;
g[par-1].pb(i);
cin >> nums[i];
}
cnt.resize(R, vector<int>(0));
for(int i = 0; i<N; i++) cnt[--nums[i]].pb(i);
int sqrt = 1;
while(sqrt*sqrt <= N) sqrt++; sqrt--;
while((R/sqrt)*N > 50000000) sqrt++;
big.resize(R, -1);
int p = 0;
for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
st.resize(N);
en.resize(N);
ans.resize(N);
above.resize(N, vector<int>(p));
dfs(0, vector<int>(R), vector<stack<int>>(p));
sums.resize(p, BIT(N));
getComp(p);
BIT b(N);
while(Q--> 0){
int up, down; cin >> up >> down; --up, --down;
if(big[up]+1 && big[down]+1) cout << precomp[big[up]][big[down]] << endl;
else if(big[up]+1){
int ret = 0;
for(int i: cnt[down]){
int u = above[i][big[up]];
if(u != -1) ret+=ans[u];
}
cout << ret << endl;
}else if(big[down]+1){
int ret = 0;
for(int i: cnt[up]) ret+=sums[big[down]].sum(st[i], en[i]);
cout << ret << endl;
}else{
int ret = 0;
for(int i: cnt[down]) b.set(st[i], 1);
for(int i: cnt[up]) ret+=b.sum(st[i], en[i])-(up == down ? 1:0);
for(int i: cnt[down]) b.set(st[i], 0);
cout << ret << endl;
}
}
}
Compilation message
regions.cpp: In function 'void dfs(int, std::vector<int>, std::vector<std::stack<int> >)':
regions.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::stack<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | else for(int i = 0; i<last.size(); i++) above[s][i] = last[i].empty() ? -1:last[i].top();
| ~^~~~~~~~~~~~
regions.cpp: In function 'void getComp(int)':
regions.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i<b.size(); i++){
| ~^~~~~~~~~
regions.cpp:70:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int j = 0; j<b.size(); j++) for(int k: cnt[b[j]])
| ~^~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:88:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
88 | while(sqrt*sqrt <= N) sqrt++; sqrt--;
| ^~~~~
regions.cpp:88:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
88 | while(sqrt*sqrt <= N) sqrt++; sqrt--;
| ^~~~
regions.cpp:92:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
92 | for(int i = 0; i<R; i++) if(cnt[i].size() >= sqrt) big[i] = p++;
| ~~~~~~~~~~~~~~^~~~~~~
regions.cpp: In function 'void setio(std::string)':
regions.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
4 ms |
208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
336 KB |
Output is correct |
| 6 |
Correct |
20 ms |
1232 KB |
Output is correct |
| 7 |
Correct |
27 ms |
464 KB |
Output is correct |
| 8 |
Correct |
33 ms |
720 KB |
Output is correct |
| 9 |
Correct |
45 ms |
7504 KB |
Output is correct |
| 10 |
Correct |
78 ms |
1624 KB |
Output is correct |
| 11 |
Correct |
160 ms |
2564 KB |
Output is correct |
| 12 |
Correct |
181 ms |
10924 KB |
Output is correct |
| 13 |
Correct |
205 ms |
2592 KB |
Output is correct |
| 14 |
Correct |
346 ms |
6580 KB |
Output is correct |
| 15 |
Correct |
427 ms |
87188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Correct |
1994 ms |
33392 KB |
Output is correct |
| 3 |
Runtime error |
82 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Correct |
462 ms |
29956 KB |
Output is correct |
| 5 |
Runtime error |
66 ms |
131072 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
126 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
140 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
75 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
125 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
93 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
655 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
299 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
118 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
148 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
96 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
108 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
96 ms |
131072 KB |
Execution killed with signal 9 |
