Submission #724995

#	Time	Username	Problem	Language	Result	Execution time	Memory
724995		FatihSolak	Regions (IOI09_regions)	C++17	100 / 100	4209 ms	59440 KiB

regions

#include <bits/stdc++.h>
#define N 200005
using namespace std;
const int magic = 500;
vector<int> adj[N];
int h[N];
int timer = 0;
int tot = 0;
int id[N];
int tin[N],tout[N];
int downval[N][N/magic + 5];
int upval[N][N/magic + 5];
int upcnt[N/magic + 5];
int sub[N];
vector<pair<int,int>> events[N];
vector<pair<int,int>> seq[N];
vector<int> nodes[N];
void dfs(int v){
    tin[v] = timer++;
    seq[tin[v]].push_back({h[v],1});
    nodes[h[v]].push_back(v);
    sub[v] = 1;
    for(auto u:adj[v]){
        dfs(u);
        sub[v] += sub[u];
    }
    tout[v] = timer;
    seq[tout[v]].push_back({h[v],-1});
}
vector<int> dfs2(int v){
    sort(adj[v].begin(),adj[v].end(),[&](int a,int b){
        return sub[a] > sub[b];
    });
    for(int i = 1;i<=tot;i++){
        upval[h[v]][i] += upcnt[i];
    }
    upcnt[id[h[v]]]++;
    vector<int> ret;
    for(auto u:adj[v]){
        if(ret.empty()){
            ret = dfs2(u);
        }
        else{
            auto tmp = dfs2(u);
            for(int i = 0;i<=tot;i++){
                ret[i] += tmp[i];
            }
        }
    }
    upcnt[id[h[v]]]--;
    if(ret.empty()){
        ret.assign(tot + 1,0);
    }
    for(int i = 1;i<=tot;i++){
        downval[h[v]][i] += ret[i];
    }
    return ret;
}

void solve(){
    int n,r,q;
    cin >> n >> r >> q;
    for(int i = 1;i<=n;i++){
        if(i > 1){
            int x;
            cin >> x;
            adj[x].push_back(i);
        }
        cin >> h[i];
    }
    for(int i = 1;i<=r;i++){
        if(nodes[i].size() > magic){
            id[i] = ++tot;
        }
    }
    dfs(1);
    dfs2(1);
    for(int i = 0;i<=n;i++){
        for(auto u:seq[i]){
            events[u.first].push_back({i,u.second});
        }
    }
    for(int i = 1;i<=q;i++){
        int r1,r2;
        cin >> r1 >> r2;
        if(id[r2] != 0){
            cout << downval[r1][id[r2]] << endl;
            continue;
        }
        if(id[r1] != 0){
            cout << upval[r2][id[r1]] << endl;
            continue;
        }
        int ans = 0;
        int cnt = 0;
        int pt = 0;
        for(auto u:nodes[r2]){
            while(pt != events[r1].size() && events[r1][pt].first <= tin[u]){
                cnt += events[r1][pt].second;
                pt++;
            }
            ans += cnt;
        }
        cout << ans << endl;
    }
}

int main(){
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while(pt != events[r1].size() && events[r1][pt].first <= tin[u]){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85