Submission #893710

#	Time	Username	Problem	Language	Result	Execution time	Memory
893710		AverageAmogusEnjoyer	Regions (IOI09_regions)	C++17	40 / 100	8063 ms	131072 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, B = 900, rax = 25000;

int n;
vector<int> adj[nax];
vector<int> nodes[rax];
int tin[nax],tout[nax],color[nax],timer=0;
ll heavy_ans[250][rax][2];
int idx[rax];

struct query1 {
    int st[4*nax];

    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);
    }
} st1;

struct query2 {
    int st[4*nax];
    void add(int l,int r,int k,int u=1,int tl=0,int tr=n-1) {
        if (l > r) {
            return;
        }
        if (l == tl && r == tr) {
            st[u] += k;
            return;
        }   
        int mid = (tl+tr)/2;
        add(l,min(r,mid),2*u,tl,mid);
        add(max(mid+1,l),r,2*u+1,mid+1,tr);
    }
    int qry(int p,int u=1,int tl=0,int tr=n-1) {
        if (tl == tr) {
            return st[u];
        }
        int mid = (tl+tr)/2;
        if (p <= mid) {
            return st[u] + qry(p,2*u,tl,mid);
        } else {
            return st[u] + qry(p,2*u+1,mid+1,tr);
        }
    }
} st2;

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);
    }
    int sz = 0;
    for (int i=0;i<r;i++) {
        idx[i] = -1;
        if ((int) nodes[i].size() >= B) {
            idx[i] = sz;
            // lui e' il figlio
            for (int &u: nodes[i]) {
                st1.upd(tin[u],1);
            }
            for (int j=0;j<n;j++) {
                if (color[j] == i) { continue; }
                heavy_ans[sz][color[j]][0] += st1.qry(tin[j],tout[j]);
            }
            for (int &u: nodes[i]) {
                st1.upd(tin[u],0);
            }
            // lui e' il padre
            for (int &u: nodes[i]) {
                st2.add(tin[u],tout[u],1);
            }
            for (int j=0;j<n;j++) {
                if (color[j] == i) { continue; }
                heavy_ans[sz][color[j]][1] += st2.qry(tin[j]);
            }
            for (int &u: nodes[i]) {
                st2.add(tin[u],tout[u],-1);
            }
            sz++;
        }
    }
    for (int a,b;q--;) {
        cin >> a >> b;
        --a,--b;
        ll ans = 0;
        if (idx[a] != -1) {
            // a is heavy
            ans = heavy_ans[idx[a]][b][1];
        } else if (idx[b] != -1) {
            // b is heavy
            ans = heavy_ans[idx[b]][a][0];
        } else {
            for (auto &x: nodes[b]) {
                st1.upd(tin[x],1);
            }
            for (auto &x: nodes[a]) {
                ans += st1.qry(tin[x],tout[x]);
            }
            for (auto &x: nodes[b]) {
                st1.upd(tin[x],0);
            }
        }
        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: 25 / 85