| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 116569 |
2019-06-13T00:22:54 Z |
kig9981 |
Regions (IOI09_regions) |
C++17 |
|
7 ms |
5680 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
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[200000], sum2[200000], tree[200001];
long long ans[rt][25000], ans2[rt][25000];
inline int get_int()
{
int ret=0;
char c=-1;
while('0'>c && c>'9') c=getchar_unlocked();
while('0'<=c && c<='9') ret*=10, ret+=c-'0', c=getchar_unlocked();
return ret;
}
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 v)
{
sum[c]+=RV[c]==v;
sum2[c]=RV[c]==v;
for(auto n: adj[c]) {
sum[n]=sum[c];
dfs2(n,v);
sum2[c]+=sum2[n];
}
}
int main()
{
int N=get_int(), M=get_int(), Q=get_int();
R[RV[0]=get_int()-1].push_back(0);
for(int i=1;i<N;i++) {
adj[get_int()-1].push_back(i);
R[RV[i]=get_int()-1].push_back(i);
}
dfs(0);
for(int i=0;i<M;i++) if(R[i].size()>=rt) {
sum[0]=0;
dfs2(0,i);
for(int j=0;j<N;j++) {
ans[O.size()][RV[j]]+=sum[j];
ans2[O.size()][RV[j]]+=sum2[j];
}
O.push_back(i);
}
while(Q--) {
int a=get_int()-1, b=get_int()-1;
if(R[a].size()>=rt) printf("%lld\n",ans[lower_bound(O.begin(),O.end(),a)-O.begin()][b]);
else if(R[b].size()>=rt) printf("%lld\n",ans2[lower_bound(O.begin(),O.end(),b)-O.begin()][a]);
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);
printf("%lld\n",ans);
}
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:66:35: warning: array subscript is below array bounds [-Warray-bounds]
for(int i=0;i<M;i++) if(R[i].size()>=rt) {
~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
6 ms |
5552 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
6 ms |
5624 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
6 ms |
5680 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
7 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
6 ms |
5652 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
6 ms |
5632 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
6 ms |
5504 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
7 ms |
5504 KB |
Unexpected end of file - int32 expected |
