oj.uz

Submission #893710

# Submission time Handle Problem Language Result Execution time Memory
893710 2023-12-27T10:08:31 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
40 / 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 = 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13400 KB Output is correct
2 Correct 2 ms 13400 KB Output is correct
3 Correct 3 ms 13400 KB Output is correct
4 Correct 4 ms 13400 KB Output is correct
5 Correct 6 ms 13400 KB Output is correct
6 Correct 11 ms 13656 KB Output is correct
7 Correct 19 ms 13656 KB Output is correct
8 Correct 29 ms 13656 KB Output is correct
9 Correct 42 ms 13912 KB Output is correct
10 Correct 103 ms 13888 KB Output is correct
11 Correct 241 ms 14168 KB Output is correct
12 Correct 233 ms 14460 KB Output is correct
13 Correct 390 ms 14744 KB Output is correct
14 Correct 801 ms 14600 KB Output is correct
15 Correct 889 ms 16816 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 131072 KB Execution killed with signal 9
2 Runtime error 104 ms 131072 KB Execution killed with signal 9
3 Runtime error 95 ms 131072 KB Execution killed with signal 9
4 Correct 665 ms 14936 KB Output is correct
5 Correct 603 ms 16236 KB Output is correct
6 Correct 4722 ms 15808 KB Output is correct
7 Correct 6357 ms 16472 KB Output is correct
8 Correct 6859 ms 20764 KB Output is correct
9 Execution timed out 8055 ms 22432 KB Time limit exceeded
10 Execution timed out 8038 ms 26740 KB Time limit exceeded
11 Execution timed out 8063 ms 23936 KB Time limit exceeded
12 Runtime error 152 ms 131072 KB Execution killed with signal 9
13 Runtime error 151 ms 131072 KB Execution killed with signal 9
14 Runtime error 147 ms 131072 KB Execution killed with signal 9
15 Runtime error 137 ms 131072 KB Execution killed with signal 9
16 Runtime error 142 ms 131072 KB Execution killed with signal 9
17 Runtime error 134 ms 131072 KB Execution killed with signal 9