Submission #1368214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368214		CowTheCow	Regions (IOI09_regions)	C++20	44 / 100	8055 ms	96276 KiB

regions

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
#define vi vector<int>
#define pb push_back
#define sz(a) a.size()
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(), a.end()

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

const int MAXN=2e5+1;
const int MAXR=25001; 
const int BIG_REGIONS=160;
const int THRESHOLD=160;

int n,r,q;
int br;

vi adj [MAXN];
vi members [MAXR];
vi member_times [MAXR];
int sz [MAXN] {0};
int get_region [MAXN] {0};
int big_idx [MAXN] {0}; //the i-th region translates to which big region? if not a big region return 0
int subtree [MAXN][BIG_REGIONS];
int ancestor [MAXN][BIG_REGIONS];
int tin [MAXN];
int tout [MAXN];
int timer=1;

void tdfs(int v, int p) {
    tin[v]=timer;
    timer++;
    for(int to:adj[v]) {
        if(to==p) continue;
        tdfs(to, v);
    }
    tout[v]=timer;
}

int sub_dfs(int v, int p, int tar) {
    int sub_cnt=0;

    if(get_region[v]==tar)
        sub_cnt++;

    for(int to:adj[v]) 
        sub_cnt+=sub_dfs(to, v, tar);

    subtree[get_region[v]][big_idx[tar]]+=sub_cnt;
    return sub_cnt;
}

void anc_dfs(int v, int p, int tar, int anc_sum) {
    if(get_region[v]==tar)
        anc_sum++;

    for(int to:adj[v])
        anc_dfs(to, v, tar, anc_sum);

    ancestor[get_region[v]][big_idx[tar]]+=anc_sum;
}

void solve() {

    cin>>n>>r>>q;

    cin>>get_region[1];
    sz[get_region[1]]++;

    for(int i=2;i<=n;i++) {
        int p,r;
        cin>>p>>r;
        get_region[i]=r;

        sz[get_region[i]]++;

        adj[p].pb(i);
    }

    //for each big region, we can just DFS, for each other node we can find how many of its children
    //are kept or ancestors
    int ptr=1;
    for(int i=1;i<=r;i++) {
        if(sz[i]>=THRESHOLD) {
            big_idx[i]=ptr;

            sub_dfs(1,-1,i);
            anc_dfs(1,-1,i,0);
            ptr++;
        }  
    }

    tdfs(1, -1);
    for(int i=1;i<=n;i++) {
        members[get_region[i]].pb(i);
        member_times[get_region[i]].pb(tin[i]);
    }
    for(int i=1;i<=r;i++) {
        if(!members[i].empty()) {
            sort(all(members[i]));
            sort(all(member_times[i]));
        }
    }
    
    for(int i=1;i<=q;i++) {
        int u,v;
        cin>>u>>v;

        if(sz[v]>=THRESHOLD) {
            cout<<subtree[u][big_idx[v]]<<"\n";
        }else if(sz[u]>=THRESHOLD) {
            cout<<ancestor[v][big_idx[u]]<<"\n";
        }else {
            //both of them are small bois
            int ans=0;
            for(int t:members[u]) {
                ans+=lower_bound(all(member_times[v]), tout[t])-lower_bound(all(member_times[v]),tin[t]);
            }
            cout<<ans<<"\n";
        }
        cout.flush();
    }
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t=1;
    // cin>>t;

    while(t>0) {
        solve();
        t--;
    }
}

Compilation message (stderr)

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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