#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{
static const int nmax=25001;
vector<int>regions;
item():regions(nmax){}
};
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(int i=1;i<=25001;++i)
{
ans.regions[i]+=a.regions[i]+b.regions[i];
}
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()
{
}
};
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);
vector<map<int,int>>regions(NMAX);
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);
for(auto [y,z]:regions[x])
regions[node][y]+=z;
}
}
tout[node]=timp;
}
segtree seg;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>r>>q;
cin>>h[1];
regions[1][h[1]]=1;
R[h[1]].pb(1);
for(int i=2;i<=n;++i)
{
cin>>s[i]>>h[i];
regions[i][h[i]]=1;
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();
// for(auto [x,y]:regions[1])
// cout<<x<<" "<<y<<nl;
while(q--)
{
ans=0;
read_query();
for(auto x:R[r1])
{
ans+=(regions[x][r2]);
}
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 function 'void dfs(int, int)':
regions.cpp:123:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
123 | for(auto [y,z]:regions[x])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
18264 KB |
Output is correct |
| 2 |
Correct |
6 ms |
18264 KB |
Output is correct |
| 3 |
Correct |
7 ms |
18264 KB |
Output is correct |
| 4 |
Correct |
8 ms |
18264 KB |
Output is correct |
| 5 |
Correct |
12 ms |
18776 KB |
Output is correct |
| 6 |
Correct |
31 ms |
24920 KB |
Output is correct |
| 7 |
Correct |
27 ms |
20824 KB |
Output is correct |
| 8 |
Correct |
35 ms |
23124 KB |
Output is correct |
| 9 |
Correct |
181 ms |
85992 KB |
Output is correct |
| 10 |
Correct |
125 ms |
37600 KB |
Output is correct |
| 11 |
Correct |
335 ms |
71164 KB |
Output is correct |
| 12 |
Runtime error |
157 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Correct |
388 ms |
69520 KB |
Output is correct |
| 14 |
Correct |
873 ms |
124432 KB |
Output is correct |
| 15 |
Runtime error |
153 ms |
131072 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
169 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
205 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
166 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
184 ms |
131072 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
173 ms |
131072 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
182 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
191 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
186 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
206 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
174 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
219 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
189 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
216 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
213 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
198 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
174 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
193 ms |
131072 KB |
Execution killed with signal 9 |
