Submission #934132

#	Time	Username	Problem	Language	Result	Execution time	Memory
934132		bobbilyking	Regions (IOI09_regions)	C++17	0 / 100	63 ms	23800 KiB

regions

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }

template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }




const ll NN = 2e5 + 1;
// const ll NN = 200;
const ll HEAVYTH = 300;
// const ll HEAVYTH = 1;
const ll AMT = NN / HEAVYTH + 2;
const ll RR = 2.5e4 + 1;

ll label[NN], tin[NN], tout[NN];
vl people[RR];
vl adj[NN];

vl dfsorder;

vl heavies;

void dfsinit(ll i) {
    static int time = 0;
    tin[i] = time++;
    dfsorder.push_back(i);
    for (auto x: adj[i]) dfsinit(x);
    tout[i] = time;
}
/*
bool isPar(ll i, ll j) {
    return tin[i] <= tin[j] and tin[j] < tout[i];
}

ll heavyRoot[AMT][RR];

void solveHeavyRoot(ll ask, ll put) {
    // compute number of ask labels on path to root, add to ans 
    vl stk;
    ll cnt = 0;

    for (auto x: dfsorder) {
        while (stk.size() and !isPar(stk.back(), x)) {
            cnt -= label[stk.back()] == ask;
            stk.pop_back();
        }
        cnt += label[x] == ask;
        stk.push_back(x);

        heavyRoot[put][label[x]] += cnt;

    }
}

ll containsHeavy[AMT][RR];

void solveContainsHeavy(ll ask, ll put) {
    // compute number of ask in subtree, then add to answer 
    vl ans(dfsorder.size() + 1);
    FD(i, ll(dfsorder.size()) - 1, -1) {
        ll x = dfsorder[i];
        for (auto y: adj[x]) ans[x] += ans[y];
        ans[x] += label[x] == ask;
        
        containsHeavy[put][label[x]] += ans[x];
    }
}
*/

namespace seg {
    typedef ll T;
    T id=0;
    T f(T a, T b) {return a+b;}

    T t[2 * NN];
    ll n=NN;  // array size

    void modify(ll p, T value) {  // set value at position p
      for (p+=n, t[p] = value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    T query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    G(n) G(r) G(q)
    
    cin >> label[1]; people[label[1]].push_back(1);
    F(i, 2, n+1) {
        G(par) cin >> label[i]; 
        adj[par].push_back(i);
        people[label[i]].push_back(i);
    }

    dfsinit(1);

    // F(i, 1, r+1) if (people[i].size() >= HEAVYTH) {
    //     heavies.push_back(i);
    // }

    // F(i, 0, heavies.size()) {
    //     solveHeavyRoot(heavies[i], i);
    // }

    // F(i, 0, heavies.size()) {
    //     solveContainsHeavy(heavies[i], i);
    // }

    // cout << heavies.size() << " vs " << r << endl;

    // exit(0);
    
    while (q--) {
        G(r1) G(r2)
        assert(r1 != r2); // i mean this is easily fixable but i dont wanna + its not well defined 

        // if (people[r1].size() >= HEAVYTH) {
        //     cout << heavyRoot[lower_bound(A(heavies), r1) - heavies.begin()][r2] << '\n';
        // } else if (people[r2].size() >= HEAVYTH) {
        //     cout << containsHeavy[lower_bound(A(heavies), r2) - heavies.begin()][r1] << '\n';
        // } else {
            for (auto x: people[r2]) seg::modify(tin[x], 1);
            ll ans = 0;
            for (auto x: people[r1]) ans += seg::query(tin[x], tout[x]);
            cout << ans << '\n';
            for (auto x: people[r2]) seg::modify(tin[x], 0);
        // }
    }
}

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