Submission #591856

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
591856	2022-07-08T04:39:01 Z	Quan2003	Regions (IOI09_regions)	C++17	80 / 100	8000 ms	36776 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<array<ll,2>>to[25001];
ll up[17][sz];
ll par[sz];
vector<ll>adj[sz];
struct compare {
 bool operator()(const array<ll,2>& value,
        const int& key)
 {
  return (value[0] < key);
 }
 bool operator()(const int& key,
     const array<ll,2>& value)
 {
  return (key < value[0]);
 }
};
 
const int mod=1e9+7;
void dfs(int u){
    to[a[u]].push_back({timer,u});
    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];
   for(int i=2;i<=n;i++){
       cin>>par[i]>>a[i];
       adj[par[i]].push_back(i);
    } 
   dfs(1);
   for(int i=0;i<q;i++){
    ll u,w,res;cin>>u>>w;
    const auto &p=to[w];res=0;
    for(auto v:to[u]){
        int x=upper_bound(p.begin(),p.end(),en[v[1]],compare())-lower_bound(p.begin(),p.end(),st[v[1]],compare());
      res+=x;
    } cout<<res<<endl;
  }
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5584 KB	Output is correct
2	Correct	3 ms	5584 KB	Output is correct
3	Correct	5 ms	5584 KB	Output is correct
4	Correct	6 ms	5584 KB	Output is correct
5	Correct	9 ms	5584 KB	Output is correct
6	Correct	18 ms	5712 KB	Output is correct
7	Correct	27 ms	5712 KB	Output is correct
8	Correct	41 ms	5712 KB	Output is correct
9	Correct	26 ms	6352 KB	Output is correct
10	Correct	82 ms	6352 KB	Output is correct
11	Correct	119 ms	6864 KB	Output is correct
12	Correct	122 ms	7708 KB	Output is correct
13	Correct	179 ms	7456 KB	Output is correct
14	Correct	239 ms	8272 KB	Output is correct
15	Correct	259 ms	12368 KB	Output is correct

Subtask #2

65.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8093 ms	12856 KB	Time limit exceeded
2	Execution timed out	8092 ms	11704 KB	Time limit exceeded
3	Execution timed out	8087 ms	15752 KB	Time limit exceeded
4	Correct	278 ms	8272 KB	Output is correct
5	Correct	373 ms	10696 KB	Output is correct
6	Correct	1099 ms	10024 KB	Output is correct
7	Correct	1407 ms	11720 KB	Output is correct
8	Correct	1136 ms	19172 KB	Output is correct
9	Correct	2127 ms	20276 KB	Output is correct
10	Correct	4185 ms	26768 KB	Output is correct
11	Correct	3504 ms	21056 KB	Output is correct
12	Correct	4142 ms	21636 KB	Output is correct
13	Correct	4816 ms	22404 KB	Output is correct
14	Correct	5926 ms	22044 KB	Output is correct
15	Correct	6791 ms	28028 KB	Output is correct
16	Correct	6704 ms	36776 KB	Output is correct
17	Execution timed out	8026 ms	35348 KB	Time limit exceeded