Submission #591852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
591852	2022-07-08T04:12:13 Z	Quan2003	Regions (IOI09_regions)	C++17	70 / 100	8000 ms	30216 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 d[sz];
ll st[sz],en[sz];
ll ans[sz];
ll a[sz];
vector<ll>col[25001];
vector<ll>to[25001];
ll up[17][sz];
ll dp[sz];
vector<ll>adj[sz];
const int mod=1e9+7;
void dfs(int u,int p){
    col[a[u]].push_back(timer);
    st[u]=timer++;
    for(auto v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
    } 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++){
       ll u;cin>>u>>a[i];
       adj[u].push_back(i);
       to[a[i]].push_back(i);
    } dfs(1,0);
      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	5 ms	6096 KB	Output is correct
2	Correct	4 ms	6108 KB	Output is correct
3	Correct	7 ms	6096 KB	Output is correct
4	Correct	9 ms	6096 KB	Output is correct
5	Correct	12 ms	6224 KB	Output is correct
6	Correct	21 ms	6224 KB	Output is correct
7	Correct	28 ms	6224 KB	Output is correct
8	Correct	37 ms	6352 KB	Output is correct
9	Correct	62 ms	6864 KB	Output is correct
10	Correct	107 ms	6864 KB	Output is correct
11	Correct	129 ms	7272 KB	Output is correct
12	Correct	184 ms	7980 KB	Output is correct
13	Correct	198 ms	7888 KB	Output is correct
14	Correct	338 ms	8624 KB	Output is correct
15	Correct	220 ms	11256 KB	Output is correct

Subtask #2

55.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8082 ms	12404 KB	Time limit exceeded
2	Execution timed out	8093 ms	11588 KB	Time limit exceeded
3	Execution timed out	8085 ms	14536 KB	Time limit exceeded
4	Correct	286 ms	8644 KB	Output is correct
5	Correct	379 ms	10180 KB	Output is correct
6	Correct	1306 ms	10124 KB	Output is correct
7	Correct	1911 ms	11680 KB	Output is correct
8	Correct	1276 ms	17080 KB	Output is correct
9	Correct	2337 ms	19272 KB	Output is correct
10	Correct	4540 ms	24000 KB	Output is correct
11	Correct	4847 ms	20108 KB	Output is correct
12	Correct	5424 ms	20852 KB	Output is correct
13	Correct	5884 ms	21124 KB	Output is correct
14	Execution timed out	8071 ms	21352 KB	Time limit exceeded
15	Execution timed out	8045 ms	25300 KB	Time limit exceeded
16	Correct	7267 ms	30216 KB	Output is correct
17	Execution timed out	8026 ms	29652 KB	Time limit exceeded