oj.uz

Submission #928028

# Submission time Handle Problem Language Result Execution time Memory
928028 2024-02-15T17:48:49 Z noyancanturk Regions (IOI09_regions) C++17
8 / 100
 3774 ms 49424 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+5;
#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=25001;

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=l;
                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;
        }
    }
}
    
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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 19032 KB Output isn't correct
2 Incorrect 5 ms 19284 KB Output isn't correct
3 Incorrect 5 ms 19032 KB Output isn't correct
4 Incorrect 6 ms 19032 KB Output isn't correct
5 Incorrect 9 ms 19032 KB Output isn't correct
6 Correct 13 ms 19032 KB Output is correct
7 Incorrect 20 ms 19032 KB Output isn't correct
8 Incorrect 17 ms 19032 KB Output isn't correct
9 Correct 28 ms 19288 KB Output is correct
10 Incorrect 44 ms 19288 KB Output isn't correct
11 Incorrect 70 ms 19544 KB Output isn't correct
12 Incorrect 78 ms 20056 KB Output isn't correct
13 Incorrect 101 ms 19628 KB Output isn't correct
14 Incorrect 161 ms 20252 KB Output isn't correct
15 Correct 209 ms 21832 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1428 ms 22644 KB Output isn't correct
2 Incorrect 1253 ms 21888 KB Output isn't correct
3 Correct 2377 ms 23984 KB Output is correct
4 Incorrect 139 ms 20312 KB Output isn't correct
5 Incorrect 206 ms 21508 KB Output isn't correct
6 Incorrect 882 ms 26480 KB Output isn't correct
7 Incorrect 1076 ms 21960 KB Output isn't correct
8 Incorrect 904 ms 26884 KB Output isn't correct
9 Incorrect 1531 ms 26148 KB Output isn't correct
10 Incorrect 3774 ms 29776 KB Output isn't correct
11 Incorrect 2476 ms 25848 KB Output isn't correct
12 Incorrect 821 ms 29548 KB Output isn't correct
13 Incorrect 1242 ms 29004 KB Output isn't correct
14 Incorrect 1421 ms 43344 KB Output isn't correct
15 Incorrect 2372 ms 32740 KB Output isn't correct
16 Incorrect 2442 ms 36168 KB Output isn't correct
17 Incorrect 2201 ms 49424 KB Output isn't correct