Submission #744202

#	Time	Username	Problem	Language	Result	Execution time	Memory
744202		hafo	Regions (IOI09_regions)	C++14	100 / 100	4647 ms	32824 KiB

regions

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;
const int sz = 450 + 7;
const int m = 25e3 + 7;

int n, st[maxn], en[maxn], timer = 0, r, q, home[maxn], cnt[maxn], r1, r2, f[sz][m], mp[m];
vector<int> g[maxn], tp[m], cp[m], large;

void dfs(int u, int par) {
    st[u] = ++timer;
    cp[home[u]].pb(timer);
    for(int i = 0; i < large.size(); i++) f[i][home[u]] += mp[large[i]];

    for(auto v:g[u]) {
        if(v == par) continue;
        mp[home[v]]++;
        dfs(v, u);
        mp[home[v]]--;
    }
    en[u] = timer;
}

int get(int l, int r, int col) {
    return upper_bound(all(cp[col]), r) - lower_bound(all(cp[col]), l);
}

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>r>>q;
    cin>>home[1];
    cnt[home[1]]++;
    for(int i = 2; i <= n; i++) {
        int x;
        cin>>x>>home[i];
        cnt[home[i]]++;
        g[x].pb(i);
    }

    mp[home[1]]++;
    for(int i = 1; i <= n; i++)
        if(cnt[home[i]] <= sz) tp[home[i]].pb(i);
    for(int i = 1; i <= r; i++)
        if(cnt[i] > sz) large.pb(i);
    dfs(1, 0);
    while(q--) {
        cin>>r1>>r2;
        if(cnt[r1] <= sz) {
            int ans = 0;
            for(auto u:tp[r1]) {
                ans += get(st[u], en[u], r2) - (r1 == r2);
            }
            cout<<ans<<endl;
        } else {
            int id = lower_bound(all(large), r1) - large.begin();
            cout<<f[id][r2]<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < large.size(); i++) f[i][home[u]] += mp[large[i]];
      |                    ~~^~~~~~~~~~~~~~

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