Submission #1367431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367431		CowTheCow	Regions (IOI09_regions)	C++20	0 / 100	1099 ms	196608 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 MAXB=160; //maximum amount of big regions
const int THRESHOLD=1;

int n,r,q;
int b; //count of bigs
vi adj [MAXN];
int region [MAXN];
int region_sz [MAXN] {0};
int big_idx [MAXN] {0};

int sub_count [MAXN][MAXB] {0};
int anc_count [MAXN][MAXB] {0};

int sub_dp [MAXR][MAXB] {0}; //for each region, how many of each big is descendant
int anc_dp [MAXR][MAXB] {0}; //for each region, how many of each big is anc

void dfs(int v, int p) {
    if(p!=-1) {
        memcpy(anc_count[v], anc_count[p], sizeof anc_count[p]);
    }

    if(big_idx[region[v]]!=0) {
        anc_count[v][big_idx[region[v]]]++;
        sub_count[v][big_idx[region[v]]]++;
    }

    for(int to:adj[v]) {
        if(to==p)
            continue;

        dfs(to, v);
        for(int i=1;i<=b;i++) 
            sub_count[v][i]+=sub_count[to][i];
    }

    for(int i=1;i<=b;i++) {
        sub_dp[region[v]][i]+=sub_count[v][i];
        anc_dp[region[v]][i]+=anc_count[v][i]; //how many ancestors current node has of type i
    }
}

void solve() {
   
    //say big is a region with size >= 160
    //there are at most 160 big regions
    //for each node, store how many bigs are children, add it to a map or something
    //therfore in 25000*160 you can find the answer for any small->big or big->big query

    cin>>n>>r>>q;

    cin>>region[1];
    for(int i=2;i<=n;i++) {
        int par;
        cin>>par>>region[i];    
        adj[par].pb(i);
    }

    for(int i=1;i<=n;i++)
        region_sz[region[i]]++;

    int p=1;
    for(int i=1;i<=r;i++) {
        if(region_sz[i]>=THRESHOLD) {
            big_idx[i]=p;
            p++;
        }
    }
    b=p-1;

    dfs(1,-1);

    for(int i=1;i<=q;i++) {
        int u,v;
        cin>>u>>v;
        
        if(big_idx[v]!=0) {
            //v is big
            cout<<sub_dp[u][v]<<"\n";
        }else if(big_idx[u]!=0){
            //u is big
            cout<<anc_dp[v][u]<<"\n";
        }else {
            //neither is big

        }

    }
}

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: 0 / 15
• Subtask 2: 0 / 85