Submission #628289

#	Time	Username	Problem	Language	Result	Execution time	Memory
628289		DeMen100ns	Regions (IOI09_regions)	C++17	100 / 100	3422 ms	46436 KiB

regions

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc

Name: Regions
Sauce: https://oj.uz/problem/view/IOI09_regions
Tag: SQRT
Sol: 

//big - big/small : precal
//small - big/small : euler tour + binsearch
Note: 
*/

#include <bits/stdc++.h>

using namespace std;

template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); } 
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

const int N = 2e5 + 5;
const long long INF = numeric_limits<long long>::max() / 2;
const int MAXA = 1e9;
const int B = sqrt(N);

vector <int> a[N], cnt[N], pos[N], node[N];
vector <int> euler;
int h[N], cntreg[N], sub[N], subp[N];

void dfs(int id, int u, int ct){
    for(int i : a[u]){
        cnt[id][h[i]] += ct;
        dfs(id, i, ct + (h[i] == id));
    }
}

void dfs_euler(int u){
    euler.push_back(u);
    for(int i : a[u]){
        dfs_euler(i);
        sub[u] += sub[i];
    }
    sub[u]++;
}

int get(vector <int> &v, int r){
    int k = upper_bound(v.begin(), v.end(), r) - v.begin();
    return k - 1;
}

void solve()
{
    int n, r, q; cin >> n >> r >> q;
    cin >> h[1]; 
    cntreg[h[1]] = 1; node[h[1]].push_back(1);
    for(int i = 2; i <= n; ++i){
        int u; cin >> u >> h[i];
        cntreg[h[i]]++;
        a[u].push_back(i);
        node[h[i]].push_back(i);
    }

    for(int i = 1; i <= r; ++i){
        if (cntreg[i] >= B){
            cnt[i].resize(r + 1);
            dfs(i, 1, (h[1] == i));
        }
    }
    dfs_euler(1);
    for(int i = 0; i < n; ++i){
        pos[h[euler[i]]].push_back(i + 1);
        subp[i + 1] = sub[euler[i]];
    }
    while (q--){
        int h1, h2;
        cin >> h1 >> h2;

        if (cntreg[h1] >= B){
            cout << cnt[h1][h2] << endl;
        } else {
            int ans = 0;
            for(int i : pos[h1]){
                ans += get(pos[h2], i + subp[i] - 1) - get(pos[h2], i - 1);
            }
            cout << ans << endl;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    int t = 1; //cin >> t;
    while (t--)
    {
        solve();
    }
}

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