Submission #893687

#	Time	Username	Problem	Language	Result	Execution time	Memory
893687		AverageAmogusEnjoyer	Regions (IOI09_regions)	C++17	50 / 100	8074 ms	28764 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

const int nax = 2e5, rax = 25000;

int st[4*nax];
int n;
vector<int> adj[nax];
vector<int> nodes[rax];
int tin[nax],tout[nax],color[nax],timer=0;
map<pair<int,int>,ll> computed;

void upd(int p,int nw,int u=1,int tl=0,int tr=n-1) {
    if (tl == tr) {
        st[u] = nw;
        return;
    }
    int mid = (tl+tr)/2;
    if (p <= mid) {
        upd(p,nw,2*u,tl,mid);
    } else {
        upd(p,nw,2*u+1,mid+1,tr);
    }
    st[u] = st[2*u] + st[2*u+1];
}

int qry(int l,int r,int u=1,int tl=0,int tr=n-1) {
    if (l > r) {
        return 0;
    }
    if (l == tl && r == tr) {
        return st[u];
    }
    int mid = (tl+tr)/2;
    return qry(l,min(r,mid),2*u,tl,mid)+qry(max(mid+1,l),r,2*u+1,mid+1,tr);
}

void dfs(int u=0,int e=-1) {
    tin[u] = timer++;
    for (int &v: adj[u]) if (v != e) {
        dfs(v,u);
    }
    tout[u] = timer-1;
}

void solve() {
    int r,q;
    cin >> n >> r >> q;
    cin >> color[0];
    for (int i=1,p;i<n;i++) {
        cin >> p >> color[i];
        --p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }
    for (int i=0;i<n;i++) {
        color[i]--;
    }
    dfs();
    for (int i=0;i<n;i++) {
        nodes[color[i]].push_back(i);
    }
    for (int a,b;q--;) {
        cin >> a >> b;
        --a,--b;
        auto c = make_pair(a,b);
        if (computed.count(c)) { cout << computed[c] << endl; continue; }
        ll ans = 0;
        // cout << "\nSon-nodes:\n";
        for (auto &x: nodes[b]) {
            // cout << x << " ";
            upd(tin[x],1);
        }
        // cout << "\nFather nodes:\n";
        for (auto &x: nodes[a]) {
            // cout << x << " ";
            ans += qry(tin[x],tout[x]);
        }
        for (auto &x: nodes[b]) {
            upd(tin[x],0);
        }
        computed[c] = ans;
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int _t = 1;
    for (int i=1;i<=_t;i++) {
        solve();
    }
}
// Dato un albero in cui ogni nodo ha un tag, query online che chiedono il numero di coppie di nodi con tag E1 ed E2, tali che
// E1 e' un antenato di E2.

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