답안 #893699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893699 2023-12-27T09:56:18 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;
int heavy_ans[B][rax][2];
int idx[rax];
map<pair<int,int>,int> computed;

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) {
            assert(sz < 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;
        auto c = make_pair(a,b);
        if (computed.count(c)) { cout << computed[c] << endl; continue; }
        int 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);
            }
        }
        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.
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 2 ms 13912 KB Output is correct
3 Correct 4 ms 14124 KB Output is correct
4 Correct 5 ms 14124 KB Output is correct
5 Correct 7 ms 15164 KB Output is correct
6 Correct 12 ms 15032 KB Output is correct
7 Correct 22 ms 15068 KB Output is correct
8 Correct 26 ms 14488 KB Output is correct
9 Correct 42 ms 15412 KB Output is correct
10 Correct 104 ms 15800 KB Output is correct
11 Correct 207 ms 15908 KB Output is correct
12 Correct 252 ms 17184 KB Output is correct
13 Correct 359 ms 17156 KB Output is correct
14 Correct 694 ms 17012 KB Output is correct
15 Correct 801 ms 19868 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 95 ms 131072 KB Execution killed with signal 9
2 Runtime error 98 ms 131072 KB Execution killed with signal 9
3 Runtime error 95 ms 131072 KB Execution killed with signal 9
4 Correct 658 ms 18020 KB Output is correct
5 Correct 627 ms 19652 KB Output is correct
6 Runtime error 87 ms 131072 KB Execution killed with signal 9
7 Runtime error 90 ms 131072 KB Execution killed with signal 9
8 Runtime error 101 ms 131072 KB Execution killed with signal 9
9 Execution timed out 8080 ms 30932 KB Time limit exceeded
10 Runtime error 132 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8045 ms 31188 KB Time limit exceeded
12 Runtime error 150 ms 131072 KB Execution killed with signal 9
13 Runtime error 147 ms 131072 KB Execution killed with signal 9
14 Runtime error 156 ms 131072 KB Execution killed with signal 9
15 Runtime error 137 ms 131072 KB Execution killed with signal 9
16 Runtime error 146 ms 131072 KB Execution killed with signal 9
17 Runtime error 155 ms 131072 KB Execution killed with signal 9