Submission #591853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
591853	2022-07-08T04:19:21 Z	Quan2003	Regions (IOI09_regions)	C++17	75 / 100	8000 ms	31760 KB

regions

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int sz=2e5+1;
ll timer=1;
int n,q,m,k,r;
ll st[sz],en[sz];
ll a[sz];
vector<ll>col[25001];
vector<ll>to[25001];
ll up[17][sz];
ll par[sz];
vector<ll>adj[sz];
const int mod=1e9+7;
void dfs(int u){
    col[a[u]].push_back(timer);
    st[u]=timer++;
    for(auto v:adj[u]){
        if(v==par[u]) continue;
        dfs(v);
    } en[u]=timer-1;
}
int main(){
   cin>>n>>r>>q; 
   cin>>a[1];
   to[a[1]].push_back(1);
   for(int i=2;i<=n;i++){
       cin>>par[i]>>a[i];
       adj[par[i]].push_back(i);
       to[a[i]].push_back(i);
    } dfs(1);
      for(int i=0;i<q;i++){
         ll u,w,res;cin>>u>>w;
         const auto &v=col[w];res=0;
         for(auto p:to[u]){
           int x=upper_bound(v.begin(),v.end(),en[p])-lower_bound(v.begin(),v.end(),st[p]);
           res+=x;
          } cout<<res<<endl;
      }
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6096 KB	Output is correct
2	Correct	4 ms	6096 KB	Output is correct
3	Correct	4 ms	6096 KB	Output is correct
4	Correct	6 ms	6096 KB	Output is correct
5	Correct	10 ms	6224 KB	Output is correct
6	Correct	18 ms	6224 KB	Output is correct
7	Correct	28 ms	6224 KB	Output is correct
8	Correct	32 ms	6352 KB	Output is correct
9	Correct	28 ms	6864 KB	Output is correct
10	Correct	97 ms	7120 KB	Output is correct
11	Correct	130 ms	7504 KB	Output is correct
12	Correct	158 ms	8144 KB	Output is correct
13	Correct	188 ms	7956 KB	Output is correct
14	Correct	308 ms	8816 KB	Output is correct
15	Correct	296 ms	11604 KB	Output is correct

Subtask #2

60.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8074 ms	12960 KB	Time limit exceeded
2	Execution timed out	8044 ms	12100 KB	Time limit exceeded
3	Execution timed out	8093 ms	15168 KB	Time limit exceeded
4	Correct	277 ms	8776 KB	Output is correct
5	Correct	403 ms	10480 KB	Output is correct
6	Correct	1454 ms	10508 KB	Output is correct
7	Correct	1877 ms	12232 KB	Output is correct
8	Correct	1354 ms	17872 KB	Output is correct
9	Correct	2420 ms	20328 KB	Output is correct
10	Correct	4338 ms	25264 KB	Output is correct
11	Correct	5367 ms	21656 KB	Output is correct
12	Correct	5546 ms	22320 KB	Output is correct
13	Correct	5818 ms	22604 KB	Output is correct
14	Correct	7903 ms	22888 KB	Output is correct
15	Execution timed out	8061 ms	26868 KB	Time limit exceeded
16	Correct	6986 ms	31760 KB	Output is correct
17	Execution timed out	8031 ms	31076 KB	Time limit exceeded