# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
835105 |
2023-08-23T08:24:40 Z |
Denkata |
Regions (IOI09_regions) |
C++17 |
|
4596 ms |
26824 KB |
#include<bits/stdc++.h>
using namespace std;
const int crit = 447;
const int maxn = 2e5+3;
const int maxr = 25003;
int i,j,p,q,n,m,R,Q,k,tin[maxn],tout[maxn],br,cnt[crit+3][maxr],hora[maxn],type[maxn],cur,d,nom[maxn];
vector <int> v[maxn];
vector <int> vid[maxr];
vector <int> kraishta[maxr];
void dfs(int u)
{
tin[u]=++br;
for(auto i:v[u])
dfs(i);
tout[u]=++br;
kraishta[type[u]].push_back(tin[u]);
}
void dfs2(int u)
{
cout<<i<<" "<<nom[i]<<" "<<type[u]<<" "<<cur<<endl;
cnt[nom[i]][type[u]]+=cur;
if(type[u]==i)
cur++;
for(auto j:v[u])
dfs2(j);
if(type[u]==i)
cur--;
}
int calc()
{
int ans = 0;
for(auto i:vid[p])
{
int l = lower_bound(kraishta[q].begin(),kraishta[q].end(),tin[i]) - kraishta[q].begin();
int r = lower_bound(kraishta[q].begin(),kraishta[q].end(),tout[i]+1) - kraishta[q].begin() - 1;
//cout<<i<<" "<<tin[i]<<" "<<tout[i]<<" "<<l<<" "<<r<<" "<<kraishta[q][l]<<" "<<kraishta[q][r]<<endl;
if(l>r)continue;
l = max(0,l);l = min(l,(int)kraishta[q].size()-1);
r = max(0,r);r = min(r,(int)kraishta[q].size()-1);
ans+=r-l+1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>R>>Q;
cin>>p;
hora[p]++;type[1] = p;vid[p].push_back(1);
for(i=2;i<=n;i++)
{
cin>>p>>q;
hora[q]++;
type[i] = q;
vid[q].push_back(i);
v[p].push_back(i);
}
dfs(1);
for(i=1;i<=R;i++)
{
if(hora[i]>=crit)
{
// cur = 0;
nom[i]=++d;
dfs2(1);
}
}
for(i=1;i<=n;i++)
sort(kraishta[i].begin(),kraishta[i].end());
while(Q--)
{
cin>>p>>q;
if(hora[p]>crit)
cout<<cnt[nom[p]][q]<<endl;
else
cout<<calc()<<endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6096 KB |
Output is correct |
2 |
Correct |
3 ms |
6096 KB |
Output is correct |
3 |
Correct |
4 ms |
6256 KB |
Output is correct |
4 |
Correct |
10 ms |
6224 KB |
Output is correct |
5 |
Correct |
8 ms |
6224 KB |
Output is correct |
6 |
Correct |
20 ms |
6224 KB |
Output is correct |
7 |
Correct |
22 ms |
6224 KB |
Output is correct |
8 |
Correct |
34 ms |
6372 KB |
Output is correct |
9 |
Correct |
47 ms |
6736 KB |
Output is correct |
10 |
Correct |
61 ms |
6736 KB |
Output is correct |
11 |
Correct |
113 ms |
6992 KB |
Output is correct |
12 |
Correct |
96 ms |
7504 KB |
Output is correct |
13 |
Correct |
172 ms |
7248 KB |
Output is correct |
14 |
Correct |
282 ms |
7760 KB |
Output is correct |
15 |
Correct |
214 ms |
10284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
19 ms |
10832 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
21 ms |
9680 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
21 ms |
12624 KB |
Time limit exceeded (wall clock) |
4 |
Correct |
240 ms |
8016 KB |
Output is correct |
5 |
Correct |
338 ms |
9424 KB |
Output is correct |
6 |
Execution timed out |
23 ms |
9188 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
22 ms |
10320 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
37 ms |
15176 KB |
Time limit exceeded (wall clock) |
9 |
Correct |
2061 ms |
15696 KB |
Output is correct |
10 |
Execution timed out |
42 ms |
20748 KB |
Time limit exceeded (wall clock) |
11 |
Correct |
4596 ms |
15616 KB |
Output is correct |
12 |
Execution timed out |
56 ms |
17180 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
50 ms |
17212 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
79 ms |
17140 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
50 ms |
21448 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
55 ms |
26824 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
64 ms |
25544 KB |
Time limit exceeded (wall clock) |