oj.uz

Submission #893687

# Submission time Handle Problem Language Result Execution time Memory
893687 2023-12-27T09:22:00 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
50 / 100
 8000 ms 28764 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, 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8544 KB Output is correct
3 Correct 2 ms 8672 KB Output is correct
4 Correct 4 ms 8936 KB Output is correct
5 Correct 6 ms 8948 KB Output is correct
6 Correct 14 ms 9304 KB Output is correct
7 Correct 20 ms 9532 KB Output is correct
8 Correct 28 ms 9344 KB Output is correct
9 Correct 44 ms 10204 KB Output is correct
10 Correct 107 ms 10440 KB Output is correct
11 Correct 249 ms 10240 KB Output is correct
12 Correct 259 ms 11564 KB Output is correct
13 Correct 374 ms 11444 KB Output is correct
14 Correct 710 ms 11860 KB Output is correct
15 Correct 918 ms 14120 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4886 ms 17272 KB Output is correct
2 Correct 5108 ms 16700 KB Output is correct
3 Execution timed out 8064 ms 20292 KB Time limit exceeded
4 Correct 719 ms 12700 KB Output is correct
5 Correct 664 ms 14736 KB Output is correct
6 Correct 891 ms 13712 KB Output is correct
7 Correct 767 ms 16200 KB Output is correct
8 Correct 5569 ms 22892 KB Output is correct
9 Execution timed out 8009 ms 25640 KB Time limit exceeded
10 Execution timed out 8050 ms 27120 KB Time limit exceeded
11 Execution timed out 8050 ms 25360 KB Time limit exceeded
12 Execution timed out 8067 ms 19668 KB Time limit exceeded
13 Execution timed out 8028 ms 19988 KB Time limit exceeded
14 Execution timed out 8074 ms 19980 KB Time limit exceeded
15 Execution timed out 8058 ms 23276 KB Time limit exceeded
16 Execution timed out 8048 ms 28764 KB Time limit exceeded
17 Execution timed out 8032 ms 27500 KB Time limit exceeded