#include <bits/stdc++.h>
#define NMAX 200001
#define pb push_back
#define eb emplace_back
#define MOD 100003
#define nl '\n'
#define INF 2147483647
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
*
*
================DEMONSTRATION===================
=====================END========================
*/
struct item{
map<int,int>regions;
};
class segtree{
private:
int n;
vector<item>tree;
public:
void init(int sz)
{
n=sz;
tree.resize(4*sz+1);
}
item neutru;
item combine(item a,item b)
{
item ans;
for(auto [x,y]:a.regions)
ans.regions[x]+=y;
for(auto [x,y]:b.regions)
ans.regions[x]+=y;
return ans;
}
void update(int node,int st,int dr,int pos,int region)
{
if(st==dr)
{
tree[node].regions[region]++;
return;
}
int mid=(st+dr)/2;
if(pos<=mid)
update(2*node,st,mid,pos,region);
else
update(2*node+1,mid+1,dr,pos,region);
tree[node]=combine(tree[2*node],tree[2*node+1]);
}
item query(int node,int st,int dr,int L,int R)
{
if(st>R || dr<L)
{
return neutru;
}
if(L<=st && dr<=R)
{
return tree[node];
}
int mid=(st+dr)/2;
item left=query(2*node,st,mid,L,R);
item right=query(2*node+1,mid+1,dr,L,R);
return combine(left,right);
}
void update(int pos,int region)
{
update(1,1,n,pos,region);
}
int query(int L,int R,int region)
{
int ans=query(1,1,n,L,R).regions[region];
return ans;
}
void check()
{
for(auto [x,y]:tree[1].regions)
{
cout<<x<<" "<<y<<nl;
}
}
};
int n,r,q;
int r1,r2,ans;
vector<int>h(NMAX),s(NMAX);
vector<int>tin(NMAX),tout(NMAX);
vector<vector<int>>G(NMAX);
vector<vector<int>>R(25001);
int timp;
void read_query()
{
cin>>r1>>r2;
}
void print_query()
{
cout.flush()<<ans<<nl;
cout.flush();
}
void dfs(int node,int parent)
{
tin[node]=++timp;
for(auto x:G[node])
{
if(x!=parent)
dfs(x,node);
}
tout[node]=timp;
}
segtree seg;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>r>>q;
cin>>h[1];
R[h[1]].pb(1);
for(int i=2;i<=n;++i)
{
cin>>s[i]>>h[i];
R[h[i]].pb(i);
G[i].pb(s[i]);
G[s[i]].pb(i);
}
dfs(1,-1);
seg.init(n);
for(int i=1;i<=n;++i)
{
seg.update(tin[i],h[i]);
}
// seg.check();
while(q--)
{
ans=0;
read_query();
for(auto x:R[r1])
{
int aux=seg.query(tin[x],tout[x],r2);
ans+=(aux);
}
print_query();
}
return 0;
}
Compilation message
regions.cpp:8: warning: "LLONG_MAX" redefined
8 | #define LLONG_MAX 9223372036854775807
|
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
from /usr/include/c++/10/climits:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
from regions.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
135 | # define LLONG_MAX __LONG_LONG_MAX__
|
regions.cpp: In member function 'item segtree::combine(item, item)':
regions.cpp:40:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | for(auto [x,y]:a.regions)
| ^
regions.cpp:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto [x,y]:b.regions)
| ^
regions.cpp: In member function 'void segtree::check()':
regions.cpp:90:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for(auto [x,y]:tree[1].regions)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
10 ms |
8792 KB |
Output is correct |
| 5 |
Correct |
75 ms |
9048 KB |
Output is correct |
| 6 |
Correct |
408 ms |
9480 KB |
Output is correct |
| 7 |
Correct |
468 ms |
9856 KB |
Output is correct |
| 8 |
Correct |
1030 ms |
10216 KB |
Output is correct |
| 9 |
Execution timed out |
8083 ms |
12368 KB |
Time limit exceeded |
| 10 |
Correct |
6935 ms |
15928 KB |
Output is correct |
| 11 |
Execution timed out |
8096 ms |
18768 KB |
Time limit exceeded |
| 12 |
Execution timed out |
8003 ms |
22892 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8021 ms |
25296 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8013 ms |
28068 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8013 ms |
36704 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8048 ms |
42688 KB |
Time limit exceeded |
| 2 |
Execution timed out |
8007 ms |
41848 KB |
Time limit exceeded |
| 3 |
Execution timed out |
8023 ms |
45428 KB |
Time limit exceeded |
| 4 |
Execution timed out |
8016 ms |
21328 KB |
Time limit exceeded |
| 5 |
Execution timed out |
8034 ms |
24284 KB |
Time limit exceeded |
| 6 |
Execution timed out |
8073 ms |
26192 KB |
Time limit exceeded |
| 7 |
Execution timed out |
8100 ms |
30288 KB |
Time limit exceeded |
| 8 |
Execution timed out |
8006 ms |
40056 KB |
Time limit exceeded |
| 9 |
Execution timed out |
8042 ms |
48720 KB |
Time limit exceeded |
| 10 |
Execution timed out |
8020 ms |
57364 KB |
Time limit exceeded |
| 11 |
Execution timed out |
8058 ms |
60052 KB |
Time limit exceeded |
| 12 |
Execution timed out |
8025 ms |
57404 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8067 ms |
57680 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8099 ms |
59732 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8031 ms |
62776 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8009 ms |
68176 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8028 ms |
66896 KB |
Time limit exceeded |
