oj.uz

Submission #921438

# Submission time Handle Problem Language Result Execution time Memory
921438 2024-02-03T20:58:12 Z Ahmed_Solyman Regions (IOI09_regions) C++14
55 / 100
 8000 ms 24784 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
const int N=2e5+5,R=25005;
vector<int>adj[N],arr[R];
int n,r,q,mark=1,t[N],s[N],e[N];
void dfs(int node,int par){
    s[node]=mark++;
    for(auto i:adj[node])
        if(i!=par)
            dfs(i,node);
    e[node]=mark-1;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
  //  freopen("input.in", "r", stdin);
  //  freopen("output.out", "w", stdout);
    #endif
    cin>>n>>r>>q;
    cin>>t[1];arr[t[1]].push_back(1);
    for(int i=2;i<=n;i++){
        int x;cin>>x;
        cin>>t[i];
        arr[t[i]].push_back(i);
        adj[x].push_back(i);
    }
    dfs(1,1);
    while(q--){
        int a,b;cin>>a>>b;
        vector<int>v;
        for(auto i:arr[b])v.push_back(s[i]);
        sort(all(v));
        int ans=0;
        for(auto i:arr[a]){
            int x=upper_bound(all(v),s[i])-v.begin();
            int y=upper_bound(all(v),e[i])-v.begin();
            ans+=y-x;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7768 KB Output is correct
3 Correct 3 ms 7768 KB Output is correct
4 Correct 3 ms 7768 KB Output is correct
5 Correct 7 ms 7768 KB Output is correct
6 Correct 11 ms 7768 KB Output is correct
7 Correct 17 ms 7768 KB Output is correct
8 Correct 20 ms 7768 KB Output is correct
9 Correct 32 ms 8280 KB Output is correct
10 Correct 61 ms 8024 KB Output is correct
11 Correct 103 ms 8464 KB Output is correct
12 Correct 127 ms 8772 KB Output is correct
13 Correct 152 ms 8536 KB Output is correct
14 Correct 289 ms 9028 KB Output is correct
15 Correct 218 ms 11360 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8045 ms 11368 KB Time limit exceeded
2 Execution timed out 8069 ms 10140 KB Time limit exceeded
3 Execution timed out 8057 ms 13064 KB Time limit exceeded
4 Correct 231 ms 9024 KB Output is correct
5 Correct 324 ms 10636 KB Output is correct
6 Correct 1520 ms 9816 KB Output is correct
7 Correct 1997 ms 10608 KB Output is correct
8 Correct 1444 ms 14972 KB Output is correct
9 Correct 2586 ms 14476 KB Output is correct
10 Correct 5060 ms 18848 KB Output is correct
11 Correct 5257 ms 13348 KB Output is correct
12 Execution timed out 8012 ms 15392 KB Time limit exceeded
13 Execution timed out 8060 ms 15572 KB Time limit exceeded
14 Execution timed out 8051 ms 16096 KB Time limit exceeded
15 Execution timed out 8026 ms 20140 KB Time limit exceeded
16 Execution timed out 8076 ms 24784 KB Time limit exceeded
17 Execution timed out 8079 ms 23736 KB Time limit exceeded