Submission #1367480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367480		CowTheCow	Regions (IOI09_regions)	C++20	3 / 100	138 ms	24156 KiB

regions

#include <bits/stdc++.h>

using namespace std;

#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=501; //use this maxR instead, get 30
const int THRESHOLD=1;

int n,r,q;
int br;

vi adj [MAXN];
int sz [MAXN] {0};
int get_region [MAXR] {0};
int hi_regions [MAXN] {0}; //add a region to this if it has enough members
int subtree [MAXR][MAXR];

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

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

    for(int to:adj[v]) {
        sub_cnt+=dfs(to, p, tar);
    }

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

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);
    }
    br=1;
    for(int i=1;i<=r;i++) {
        if(sz[i]>=THRESHOLD) {
            hi_regions[br]=i;
            br++;
        }
    }
    br--; //br represents count of big regions

    //for each big region, we can just DFS, for each other node we can find how many of its children
    //are kept or ancestors
    for(int i=1;i<=r;i++) {
        dfs(1,-1,i);
    }

    for(int i=1;i<=q;i++) {
        int u,v;
        cin>>u>>v;

        cout<<subtree[u][v]<<"\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:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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 + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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