oj.uz

Submission #928023

# Submission time Handle Problem Language Result Execution time Memory
928023 2024-02-15T17:42:56 Z noyancanturk Regions (IOI09_regions) C++17
8 / 100
 2519 ms 131072 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(0<=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 23128 KB Output isn't correct
2 Incorrect 5 ms 23128 KB Output isn't correct
3 Incorrect 7 ms 23128 KB Output isn't correct
4 Incorrect 7 ms 23128 KB Output isn't correct
5 Incorrect 9 ms 23128 KB Output isn't correct
6 Correct 21 ms 25432 KB Output is correct
7 Incorrect 22 ms 24152 KB Output isn't correct
8 Incorrect 23 ms 24920 KB Output isn't correct
9 Correct 46 ms 27680 KB Output is correct
10 Incorrect 81 ms 30816 KB Output isn't correct
11 Incorrect 92 ms 27332 KB Output isn't correct
12 Incorrect 146 ms 32272 KB Output isn't correct
13 Incorrect 156 ms 29016 KB Output isn't correct
14 Incorrect 193 ms 26120 KB Output isn't correct
15 Correct 246 ms 28476 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1608 ms 28788 KB Output isn't correct
2 Incorrect 1443 ms 28712 KB Output isn't correct
3 Correct 2519 ms 31592 KB Output is correct
4 Runtime error 327 ms 131072 KB Execution killed with signal 9
5 Runtime error 435 ms 131072 KB Execution killed with signal 9
6 Runtime error 354 ms 131072 KB Execution killed with signal 9
7 Runtime error 357 ms 131072 KB Execution killed with signal 9
8 Runtime error 392 ms 131072 KB Execution killed with signal 9
9 Runtime error 473 ms 131072 KB Execution killed with signal 9
10 Runtime error 371 ms 131072 KB Execution killed with signal 9
11 Runtime error 476 ms 131072 KB Execution killed with signal 9
12 Runtime error 614 ms 131072 KB Execution killed with signal 9
13 Runtime error 522 ms 131072 KB Execution killed with signal 9
14 Runtime error 534 ms 131072 KB Execution killed with signal 9
15 Runtime error 382 ms 131072 KB Execution killed with signal 9
16 Runtime error 369 ms 131072 KB Execution killed with signal 9
17 Runtime error 456 ms 131072 KB Execution killed with signal 9