oj.uz

Submission #893708

# Submission time Handle Problem Language Result Execution time Memory
893708 2023-12-27T10:05:44 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
25 / 100
 8000 ms 131072 KB 
#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 = 450, rax = 25000;

int n;
vector<int> adj[nax];
vector<int> nodes[rax];
int tin[nax],tout[nax],color[nax],timer=0;
ll heavy_ans[B][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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13912 KB Output is correct
2 Correct 2 ms 13912 KB Output is correct
3 Correct 3 ms 13912 KB Output is correct
4 Correct 5 ms 13912 KB Output is correct
5 Correct 6 ms 13912 KB Output is correct
6 Correct 12 ms 13912 KB Output is correct
7 Correct 22 ms 13912 KB Output is correct
8 Correct 29 ms 13912 KB Output is correct
9 Correct 45 ms 14168 KB Output is correct
10 Correct 93 ms 14168 KB Output is correct
11 Correct 236 ms 14424 KB Output is correct
12 Correct 237 ms 14892 KB Output is correct
13 Correct 388 ms 14680 KB Output is correct
14 Correct 818 ms 15036 KB Output is correct
15 Correct 878 ms 17456 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 131072 KB Execution killed with signal 9
2 Runtime error 92 ms 131072 KB Execution killed with signal 9
3 Runtime error 98 ms 131072 KB Execution killed with signal 9
4 Correct 628 ms 15192 KB Output is correct
5 Correct 604 ms 16504 KB Output is correct
6 Runtime error 92 ms 131072 KB Execution killed with signal 9
7 Runtime error 104 ms 131072 KB Execution killed with signal 9
8 Runtime error 96 ms 131072 KB Execution killed with signal 9
9 Execution timed out 8032 ms 22980 KB Time limit exceeded
10 Runtime error 123 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8026 ms 24180 KB Time limit exceeded
12 Runtime error 156 ms 131072 KB Execution killed with signal 9
13 Runtime error 134 ms 131072 KB Execution killed with signal 9
14 Runtime error 149 ms 131072 KB Execution killed with signal 9
15 Runtime error 147 ms 131072 KB Execution killed with signal 9
16 Runtime error 145 ms 131072 KB Execution killed with signal 9
17 Runtime error 137 ms 131072 KB Execution killed with signal 9