제출 #933386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933386		themm1	Inside information (BOI21_servers)	C++17	0 / 100	144 ms	1992 KiB

servers

#include <bits/stdc++.h>
using namespace std;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &pr) {out << "(" << pr.first << "; " << pr.second << ")";return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &s) {out << "{";for(const auto &x : s)out << x << ", ";out << "}";return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &m) {out << "{";for(const auto &x : m)out << x << ", ";out << "}";return out;}
template<class T>
ostream& operator<<(ostream& out, const vector<T> &a){out << "[";for(const auto &x : a)out << x << ", ";out << "]";return out;}

#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

struct DSU {
        int N;
        vector<int> parents, heights;
        DSU(int n) {
                N = n;
                parents.assign(N, -1);
                heights.assign(N, 1);
        }

        int find_set(int u) {
                if (parents[u] == -1) return u;
                return find_set(parents[u]);
        }

        void unite(int u, int v) {
                u = find_set(u);
                v = find_set(v);
                if (u == v) return;
                if (heights[u] < heights[v]) swap(u, v);
                if (heights[u] == heights[v]) heights[u]++;
                parents[v] = u;
        }
};

struct Query {
        int u, v, idx;
};

struct Up {
        int u = 0, first_edge = 0, last_edge = 0;
        bool incr = true, decr = true;
};

int N, K, LOG = 3;
vector<vector<pii>> adj;
vector<vector<Up>> ups;
vector<int> answers, parents, intimes, outtimes;

void preprocess_dfs(int u, int p, int &time, int prev_edge_id = 0) {
        intimes[u] = time++;
        parents[u] = p;

        ups[u][0] = { p, prev_edge_id, prev_edge_id, true, true };
        for (int i = 1; i < LOG; i++) {
                Up prev = ups[u][i - 1];
                Up next = ups[prev.u][i - 1];
                bool incr = prev.last_edge < next.first_edge;
                ups[u][i] = {
                        next.u,
                        prev.first_edge,
                        next.last_edge,
                        (prev.incr && next.incr && (incr || next.first_edge == 0)),
                        (prev.decr && next.decr && (!incr || next.first_edge == 0))
                };
                // dmpn(u); dmpn(next.u); dmpn(ups[u][i].incr); dmp(ups[u][i].decr);
        }

        for (auto [id, v] : adj[u]) {
                if (v != p) {
                        preprocess_dfs(v, u, time, id);
                }
        }
        outtimes[u] = time++;
}

// Whether u is ancestor of v.
bool is_ancestor(int u, int v) {
        return (intimes[u] <= intimes[v] && outtimes[u] >= outtimes[v]);
}

int lca(int u, int v) {
        if (is_ancestor(u, v)) return u;
        if (is_ancestor(v, u)) return v;

        for (int i = LOG - 1; i >= 0; i--) {
                int next = ups[u][i].u;
                if (!is_ancestor(next, v)) u = next;
        }
        return parents[u];
}

bool path_increasing(int u, int v) {
        int lanc = lca(u, v);

        bool incr = true;
        for (int i = LOG - 1, x = u; i >= 0; i--) {
                Up next = ups[x][i];
                if (!is_ancestor(next.u, v) || next.u == lanc) {
                        x = next.u;
                        if (!next.incr) incr = false;
                }
        }
        bool decr = true;
        for (int i = LOG - 1, x = v; i >= 0; i--) {
                Up next = ups[x][i];
                if (!is_ancestor(next.u, u) || next.u == lanc) {
                        x = next.u;
                        if (!next.decr) decr = false;
                }
        }
        return incr && decr;
}

int bruteforce_dfs(int u, int p, int target, int prev_edge_id = 0) {
        int cnt = (target == -1 || u == target);
        for (auto [id, v] : adj[u]) {
                if (v != p && id > prev_edge_id) {
                        cnt += bruteforce_dfs(v, u, target, id);
                }
        }
        return cnt;
}

void solve() {
        cin >> N >> K;
        adj.assign(N, {});
        ups.assign(N, vector<Up>(LOG, Up{}));

        answers.assign(K, -3);
        intimes.assign(N, -1);
        outtimes.assign(N, -1);
        parents.assign(N, -1);

        DSU dsu(N);
        int Q = N - 1 + K, query_idx = 0, edge_idx = 1;
        vector<Query> queries;
        while (Q--) {
                char type;
                int u;
                cin >> type >> u;
                u--;
                if (type == 'S') {
                        int v;
                        cin >> v;
                        v--;

                        adj[u].pb({ edge_idx, v });
                        adj[v].pb({ edge_idx, u });
                        dsu.unite(u, v);
                        edge_idx++;
                } else if (type == 'Q') {
                        int v;
                        cin >> v;
                        v--;

                        if (dsu.find_set(u) != dsu.find_set(v)) {
                                answers[query_idx] = -2;
                        } else {
                                queries.pb({ u, v, query_idx });
                        }
                        query_idx++;
                } else {
                        answers[query_idx] = bruteforce_dfs(u, -1, -1);
                        query_idx++;
                }
        }
        int time = 0;
        preprocess_dfs(0, 0, time);
        for (Query q : queries) {
                if (path_increasing(q.v, q.u)) answers[q.idx] = -1;
                else answers[q.idx] = -2;
        }
        for (int x : answers) {
                if (x == -1) cout << "yes" << endl;
                else if (x == -2) cout << "no" << endl;
                else cout << x << endl;
        }
}

int32_t main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5