oj.uz

Submission #928024

# Submission time Handle Problem Language Result Execution time Memory
928024 2024-02-15T17:44:50 Z noyancanturk Regions (IOI09_regions) C++17
8 / 100
 3753 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 7 ms 19032 KB Output isn't correct
2 Incorrect 6 ms 19032 KB Output isn't correct
3 Incorrect 6 ms 19032 KB Output isn't correct
4 Incorrect 6 ms 19032 KB Output isn't correct
5 Incorrect 8 ms 19032 KB Output isn't correct
6 Correct 12 ms 19064 KB Output is correct
7 Incorrect 19 ms 19032 KB Output isn't correct
8 Incorrect 23 ms 19032 KB Output isn't correct
9 Correct 27 ms 19288 KB Output is correct
10 Incorrect 41 ms 19288 KB Output isn't correct
11 Incorrect 79 ms 19548 KB Output isn't correct
12 Incorrect 87 ms 20056 KB Output isn't correct
13 Incorrect 98 ms 19800 KB Output isn't correct
14 Incorrect 183 ms 20144 KB Output isn't correct
15 Correct 208 ms 21860 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1449 ms 22736 KB Output isn't correct
2 Incorrect 1239 ms 21860 KB Output isn't correct
3 Correct 2399 ms 24160 KB Output is correct
4 Incorrect 141 ms 20164 KB Output isn't correct
5 Incorrect 229 ms 21356 KB Output isn't correct
6 Incorrect 685 ms 26480 KB Output isn't correct
7 Incorrect 1031 ms 21872 KB Output isn't correct
8 Incorrect 873 ms 27352 KB Output isn't correct
9 Incorrect 1515 ms 26180 KB Output isn't correct
10 Incorrect 3753 ms 29584 KB Output isn't correct
11 Incorrect 2582 ms 25848 KB Output isn't correct
12 Incorrect 793 ms 29556 KB Output isn't correct
13 Incorrect 1229 ms 29004 KB Output isn't correct
14 Incorrect 1379 ms 43280 KB Output isn't correct
15 Incorrect 2298 ms 32724 KB Output isn't correct
16 Incorrect 2480 ms 36172 KB Output isn't correct
17 Incorrect 2296 ms 49424 KB Output isn't correct