#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int rt=448;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], PS[rt][200000], tree[200001];
pair<long long,long long> ans[rt][25000];
void add_tree(int n, int v)
{
for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}
int get_sum(int n)
{
int ret=0;
for(++n;n;n-=n&-n) ret+=tree[n];
return ret;
}
int get_sum(int s, int e)
{
return get_sum(e)-get_sum(s-1);
}
void dfs(int c)
{
num[c]=++node_cnt;
for(auto n: adj[c]) dfs(n);
fin[c]=node_cnt;
}
void dfs2(int c, int idx)
{
if(RV[c]==O[idx]) {
sum[idx][c]++;
PS[idx][num[c]]++;
}
for(auto n: adj[c]) {
sum[idx][n]=sum[idx][c];
dfs2(n,idx);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M, Q, p;
cin>>N>>M>>Q>>RV[0];
R[--RV[0]].push_back(0);
for(int i=1;i<N;i++) {
cin>>p>>RV[i];
adj[--p].push_back(i);
R[--RV[i]].push_back(i);
}
dfs(0);
for(int i=0;i<M;i++) if(R[i].size()>=rt) {
O.push_back(i);
dfs2(0,O.size()-1);
for(int j=0;j<O.size()-1;j++) {
for(auto r: R[i]) ans[O.size()-1][O[j]].first+=sum[j][r];
for(auto r: R[O[j]]) ans[j][O.back()].first+=sum[O.size()-1][r];
}
}
for(int i=0;i<O.size();i++) {
for(int j=1;j<N;j++) PS[i][j]+=PS[i][j-1];
for(int j=0;j<M;j++) if(R[j].size()<rt) for(auto r: R[j]) {
ans[i][j].first+=sum[i][r];
ans[i][j].second+=PS[i][fin[r]]-(num[r] ? PS[i][num[r]-1]:0);
}
}
while(Q--) {
int a, b;
cin>>a>>b; --a; --b;
if(R[a].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),a)-O.begin()][b].first<<'\n';
else if(R[b].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),b)-O.begin()][a].second<<'\n';
else {
long long ans=0;
for(auto r: R[b]) add_tree(num[r],1);
for(auto r: R[a]) ans+=get_sum(num[r],fin[r]);
for(auto r: R[b]) add_tree(num[r],-1);
cout<<ans<<'\n';
}
cout.flush();
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<O.size()-1;j++) {
~^~~~~~~~~~~
regions.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<O.size();i++) {
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5760 KB |
Output is correct |
2 |
Correct |
6 ms |
5760 KB |
Output is correct |
3 |
Correct |
7 ms |
5632 KB |
Output is correct |
4 |
Correct |
11 ms |
5632 KB |
Output is correct |
5 |
Correct |
12 ms |
5760 KB |
Output is correct |
6 |
Correct |
23 ms |
5760 KB |
Output is correct |
7 |
Correct |
37 ms |
5760 KB |
Output is correct |
8 |
Correct |
36 ms |
5760 KB |
Output is correct |
9 |
Correct |
63 ms |
6016 KB |
Output is correct |
10 |
Correct |
81 ms |
6144 KB |
Output is correct |
11 |
Correct |
172 ms |
6400 KB |
Output is correct |
12 |
Correct |
148 ms |
6784 KB |
Output is correct |
13 |
Correct |
283 ms |
6528 KB |
Output is correct |
14 |
Correct |
356 ms |
7156 KB |
Output is correct |
15 |
Correct |
511 ms |
8960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1707 ms |
19704 KB |
Output isn't correct |
2 |
Incorrect |
1874 ms |
17272 KB |
Output isn't correct |
3 |
Incorrect |
4030 ms |
19072 KB |
Output isn't correct |
4 |
Correct |
406 ms |
7168 KB |
Output is correct |
5 |
Correct |
395 ms |
8368 KB |
Output is correct |
6 |
Incorrect |
805 ms |
40184 KB |
Output isn't correct |
7 |
Correct |
2205 ms |
20736 KB |
Output is correct |
8 |
Correct |
1763 ms |
109628 KB |
Output is correct |
9 |
Correct |
5246 ms |
14248 KB |
Output is correct |
10 |
Incorrect |
5420 ms |
119680 KB |
Output isn't correct |
11 |
Execution timed out |
8052 ms |
13960 KB |
Time limit exceeded |
12 |
Correct |
2623 ms |
19236 KB |
Output is correct |
13 |
Correct |
3565 ms |
19448 KB |
Output is correct |
14 |
Incorrect |
4345 ms |
57164 KB |
Output isn't correct |
15 |
Incorrect |
6483 ms |
23768 KB |
Output isn't correct |
16 |
Correct |
6335 ms |
29224 KB |
Output is correct |
17 |
Incorrect |
5490 ms |
67504 KB |
Output isn't correct |