oj.uz

Submission #928280

# Submission time Handle Problem Language Result Execution time Memory
928280 2024-02-16T07:11:12 Z noyancanturk Regions (IOI09_regions) C++17
100 / 100
 4210 ms 54288 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+100;
#else
    const int lim=3e3+3;
#endif

#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int mod=1e9+7;
//const int mod=(1ll<<61)-1;

using pii=pair<int,int>;

const int rlim=25100;

int tribe[lim],parent[lim];
vector<int>v[lim],tr[rlim];
int tin[lim],tout[lim],hastin[lim],tt=1;
unordered_map<int,int>anss[lim];

void tour(int node){
    hastin[tin[node]=tt++]=node;
    for(int j:v[node]){
        tour(j);
    }
    tout[node]=tt;
}

inline void solve(){
    int n,r,q;
    cin>>n>>r>>q;
    cin>>tribe[1];
    tr[tribe[1]].pb(1);
    for(int i=2;i<=n;i++){
        cin>>parent[i];
        v[parent[i]].pb(i);
        cin>>tribe[i];
        tr[tribe[i]].pb(i);
    }
    tour(1);
    for(int i=1;i<=r;i++){
        sort(tr[i].begin(),tr[i].end(),
        [&](int x,int y) -> bool {
            return tin[x]<tin[y];
        });
        if(500<=tr[i].size()){
            int dif[n+5];
            memset(dif,0,sizeof(dif));
            for(int j:tr[i]){
                dif[tin[j]]++;
                dif[tout[j]]--;
            }
            int cur=0;
            for(int j=1;j<=tt;j++){
                cur+=dif[j];
                anss[i][tribe[hastin[j]]]+=cur;
            }
        }
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        if(tr[a].size()<=500){
            int ans=0;
            for(int j:tr[a]){
                int l=0,r=tr[b].size()-1,first=-1,last=-1;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(tin[j]<tin[tr[b][mid]]){
                        first=mid;
                        r=mid-1;
                    }else{
                        l=mid+1;
                    }
                }
                if(first==-1){
                    continue;
                }
                l=first,r=tr[b].size()-1;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(tin[tr[b][mid]]<tout[j]){
                        last=mid;
                        l=mid+1;
                    }else{
                        r=mid-1;
                    }
                }
                if(first<=last){
                    ans+=last-first+1;
                }
            }
            cout<<ans<<endl;
        }else{
            cout<<anss[a][b]<<endl;
        }
        cout.flush();
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 6 ms 23128 KB Output is correct
4 Correct 6 ms 23128 KB Output is correct
5 Correct 8 ms 23128 KB Output is correct
6 Correct 14 ms 23128 KB Output is correct
7 Correct 19 ms 23128 KB Output is correct
8 Correct 18 ms 23128 KB Output is correct
9 Correct 27 ms 23384 KB Output is correct
10 Correct 56 ms 23640 KB Output is correct
11 Correct 86 ms 23704 KB Output is correct
12 Correct 103 ms 24040 KB Output is correct
13 Correct 112 ms 23896 KB Output is correct
14 Correct 163 ms 24240 KB Output is correct
15 Correct 200 ms 26104 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 27228 KB Output is correct
2 Correct 1437 ms 26868 KB Output is correct
3 Correct 2640 ms 28504 KB Output is correct
4 Correct 151 ms 24308 KB Output is correct
5 Correct 235 ms 25580 KB Output is correct
6 Correct 940 ms 30872 KB Output is correct
7 Correct 1151 ms 26304 KB Output is correct
8 Correct 1057 ms 31152 KB Output is correct
9 Correct 1576 ms 31008 KB Output is correct
10 Correct 4210 ms 34460 KB Output is correct
11 Correct 2680 ms 31320 KB Output is correct
12 Correct 859 ms 35072 KB Output is correct
13 Correct 1330 ms 34640 KB Output is correct
14 Correct 1405 ms 49056 KB Output is correct
15 Correct 2475 ms 37416 KB Output is correct
16 Correct 2751 ms 40812 KB Output is correct
17 Correct 2453 ms 54288 KB Output is correct