oj.uz

Submission #921461

# Submission time Handle Problem Language Result Execution time Memory
921461 2024-02-03T22:19:25 Z Ahmed_Solyman Regions (IOI09_regions) C++14
75 / 100
 8000 ms 131072 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,B=447;
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);
    map<pair<int,int>,int>mp;
    for(int i=1;i<=r;i++){
        if(arr[i].size()>=B){
            for(int j=1;j<=r;j++){
                vector<int>v;
                int cnt=0;
                for(auto x:arr[j])v.push_back(s[x]);
                sort(all(v));
                for(auto g:arr[i]){
                    int x=upper_bound(all(v),s[g])-v.begin();
                    int y=upper_bound(all(v),e[g])-v.begin();
                    cnt+=y-x;
                }
                mp[{i,j}]=cnt;
            }
        }
    }
    for(int j=1;j<=r;j++){
        if(arr[j].size()>=B){
            vector<int>v;
            for(auto x:arr[j])v.push_back(s[x]);
            sort(all(v));
            for(int i=1;i<=r;i++){
                int cnt=0;
                for(auto g:arr[i]){
                    int x=upper_bound(all(v),s[g])-v.begin();
                    int y=upper_bound(all(v),e[g])-v.begin();
                    cnt+=y-x;
                }
                mp[{i,j}]=cnt;
            }
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        if(arr[a].size()>=B || arr[b].size()>=B){
            cout<<mp[{a,b}]<<endl;
            continue;
        }
        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 4 ms 7768 KB Output is correct
4 Correct 3 ms 7768 KB Output is correct
5 Correct 5 ms 7852 KB Output is correct
6 Correct 11 ms 7768 KB Output is correct
7 Correct 15 ms 7768 KB Output is correct
8 Correct 20 ms 7768 KB Output is correct
9 Correct 29 ms 8280 KB Output is correct
10 Correct 61 ms 8280 KB Output is correct
11 Correct 96 ms 8280 KB Output is correct
12 Correct 106 ms 8892 KB Output is correct
13 Correct 144 ms 8304 KB Output is correct
14 Correct 285 ms 8824 KB Output is correct
15 Correct 231 ms 11400 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1464 ms 11708 KB Output is correct
2 Correct 1651 ms 10420 KB Output is correct
3 Correct 2706 ms 13136 KB Output is correct
4 Correct 243 ms 9048 KB Output is correct
5 Correct 258 ms 10636 KB Output is correct
6 Correct 3404 ms 62728 KB Output is correct
7 Correct 2502 ms 32120 KB Output is correct
8 Runtime error 5389 ms 131072 KB Execution killed with signal 9
9 Correct 2263 ms 14268 KB Output is correct
10 Runtime error 5941 ms 131072 KB Execution killed with signal 9
11 Correct 4695 ms 13344 KB Output is correct
12 Correct 6558 ms 19772 KB Output is correct
13 Correct 6466 ms 19548 KB Output is correct
14 Execution timed out 8010 ms 23380 KB Time limit exceeded
15 Execution timed out 8020 ms 21828 KB Time limit exceeded
16 Correct 7453 ms 30840 KB Output is correct
17 Execution timed out 8102 ms 49568 KB Time limit exceeded