Submission #933361

# Submission time Handle Problem Language Result Execution time Memory
933361 2024-02-25T14:50:37 Z themm1 Inside information (BOI21_servers) C++17
0 / 100
148 ms 2008 KB
#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 Edge {
        int parent = 0, child = 0, id = 0;
};

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<Edge>> adj;
vector<Edge> edges;
vector<vector<Up>> ups;
vector<int> answers, intimes, outtimes;

void preprocess_dfs(int u, int p, int &time) {
        intimes[u] = time++;
        int parent_edge = 0;
        for (Edge &e : adj[u]) {
                if ((e.child == p && e.parent == u) || (e.parent != p && e.child == u)) {
                        swap(e.child, e.parent);
                }
                if (e.parent == p && e.child == u) parent_edge = e.id;
        }

        ups[u][0] = { p, parent_edge, parent_edge, 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 (Edge e : adj[u]) {
                if (e.parent == u) {
                        preprocess_dfs(e.child, u, time);
                }
        }
        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;
        }
        for (Edge e : adj[u]) if (e.child == u) return e.parent;
        return 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;
}

void solve() {
        cin >> N >> K;
        adj.assign(N, {});
        edges.assign(N, {});
        answers.assign(K, -3);
        intimes.assign(N, -1);
        outtimes.assign(N, -1);
        ups.assign(N, vector<Up>(LOG, Up{}));

        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--;

                        Edge e = { u, v, edge_idx };
                        edges[edge_idx] = e;
                        adj[u].pb(e);
                        adj[v].pb(e);
                        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] = -4;
                        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();
        }
}

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 1688 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 1688 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 1980 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 1980 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 2008 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 2008 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 1544 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 1544 KB Output isn't correct
2 Halted 0 ms 0 KB -