oj.uz

Submission #893715

# Submission time Handle Problem Language Result Execution time Memory
893715 2023-12-27T10:12:56 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
40 / 100
 8000 ms 27788 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 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 8 ms 8792 KB Output is correct
6 Correct 14 ms 9088 KB Output is correct
7 Correct 19 ms 9300 KB Output is correct
8 Correct 25 ms 9048 KB Output is correct
9 Correct 47 ms 9500 KB Output is correct
10 Correct 104 ms 9512 KB Output is correct
11 Correct 229 ms 9560 KB Output is correct
12 Correct 236 ms 12168 KB Output is correct
13 Correct 375 ms 12176 KB Output is correct
14 Correct 797 ms 12376 KB Output is correct
15 Correct 887 ms 14676 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8013 ms 14628 KB Time limit exceeded
2 Execution timed out 8044 ms 14132 KB Time limit exceeded
3 Execution timed out 8042 ms 16068 KB Time limit exceeded
4 Correct 644 ms 12460 KB Output is correct
5 Correct 628 ms 13748 KB Output is correct
6 Correct 4612 ms 13512 KB Output is correct
7 Correct 6286 ms 14164 KB Output is correct
8 Correct 6408 ms 18236 KB Output is correct
9 Execution timed out 8087 ms 18048 KB Time limit exceeded
10 Execution timed out 8013 ms 22264 KB Time limit exceeded
11 Execution timed out 8013 ms 19472 KB Time limit exceeded
12 Execution timed out 8042 ms 18368 KB Time limit exceeded
13 Execution timed out 8009 ms 19304 KB Time limit exceeded
14 Execution timed out 8092 ms 19292 KB Time limit exceeded
15 Execution timed out 8006 ms 22364 KB Time limit exceeded
16 Execution timed out 8039 ms 27788 KB Time limit exceeded
17 Execution timed out 8087 ms 26484 KB Time limit exceeded