제출 #1131993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131993		woohyun_jng	Inside information (BOI21_servers)	C++20	0 / 100	43 ms	52280 KiB

servers

#include <bits/stdc++.h>
#define int long long

#define MAX 230100

using namespace std;
typedef pair<int, int> pr;

vector<pr> adj[MAX];
vector<int> node_q[MAX], arr, upd[MAX];
map<int, int> mp[MAX][2], parent_ln[MAX];
int Q, sz[MAX], parent[MAX], ans[MAX], tree[MAX * 4];
bool vst[MAX];

int query(int l, int r) {
    int res = 0;
    for (l += Q, r += Q + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += tree[l++];
        if (r & 1)
            res += tree[--r];
    }
    return res;
}

void update(int idx, int val) {
    for (tree[idx += Q] += val; idx > 1; idx >>= 1)
        tree[idx >> 1] = tree[idx] + tree[idx ^ 1];
}

int get_size(int node, int par) {
    int res = 1;
    for (pr i : adj[node]) {
        if (i.first == par || vst[i.first])
            continue;
        res += get_size(i.first, node);
    }
    return sz[node] = res;
}

int get_centroid(int node, int par, int cap) {
    for (pr i : adj[node]) {
        if (i.first == par || vst[i.first])
            continue;
        if (sz[i.first] * 2 > cap)
            return get_centroid(i.first, node, cap);
    }
    return node;
}

void dfs(int node, int par, int cent, int time, int first, int type) {
    if (type == 0)
        upd[time].push_back(first), arr.push_back(time);
    if (type == 1) {
        for (int i : node_q[node])
            upd[i].push_back(-node), arr.push_back(i);
    }
    mp[cent][type][node] = first;

    for (pr i : adj[node]) {
        if (i.first == par || vst[i.first])
            continue;
        if ((i.second > time) ^ type) // type -> 0 이면 cent에서 내려감 1이면 올라감
            dfs(i.first, node, cent, i.second, first, type);
    }
}

void upd_dfs(int node, int par, int cent, int time) {
    parent_ln[node][cent] = time;
    for (pr i : adj[node]) {
        if (i.first == par || vst[i.first])
            continue;
        upd_dfs(i.first, node, cent, i.second);
    }
}

void build_tree(int node, int par) {
    int cent = get_centroid(node, -1, get_size(node, -1));
    vst[cent] = true, parent[cent] = par;

    mp[cent][0][cent] = Q, mp[cent][1][cent] = -1, parent_ln[cent][cent] = -1;
    upd[0].push_back(Q - 1), arr.push_back(0);
    for (int i : node_q[cent])
        upd[i].push_back(-cent), arr.push_back(i);

    for (pr i : adj[cent]) {
        if (vst[i.first])
            continue;
        dfs(i.first, cent, cent, i.second, i.second, 0);
        dfs(i.first, cent, cent, i.second, i.second, 1);
        upd_dfs(i.first, cent, cent, i.second);
    }

    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    for (int i : arr) {
        sort(upd[i].begin(), upd[i].end(), greater<int>());
        for (int j : upd[i]) {
            if (j >= 0)
                update(j, 1);
            else
                ans[i] += query(-j == cent ? 0 : mp[cent][1][-j] + 1, Q - 1);
        }
    }

    for (int i : arr) {
        for (int j : upd[i])
            if (j >= 0)
                update(j, -1);
        upd[i].clear();
    }
    arr.clear();

    for (pr i : adj[cent]) {
        if (vst[i.first])
            continue;
        build_tree(i.first, cent);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, K, A, B, T, X, res;
    vector<pr> queries;
    char C;

    cin >> N >> K;

    for (int i = 0; i < N + K - 1; i++) {
        cin >> C;
        if (C == 'S') {
            cin >> A >> B;
            adj[A].push_back({B, i}), adj[B].push_back({A, i});
            queries.push_back({-1, -1});
        } else if (C == 'Q') {
            cin >> A >> B;
            queries.push_back({A, B});
        } else {
            cin >> A;
            queries.push_back({A, 0}), node_q[A].push_back(i);
        }
    }
    Q = N + K - 1;

    build_tree(1, -1);

    for (int i = 0; i < N + K - 1; i++) {
        A = queries[i].first, B = queries[i].second;
        if (B == -1)
            continue;
        if (B != 0) {
            X = A, res = 0;
            while (X != -1) {
                if (mp[X][1].find(B) != mp[X][1].end() && mp[X][0].find(A) != mp[X][0].end())
                    res |= mp[X][1][B] < mp[X][0][A] && parent_ln[A][X] <= i;
                X = parent[X];
            }
            cout << (res ? "yes" : "no") << '\n';
        } else
            cout << ans[i] << '\n';
    }

    return 0;
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18