oj.uz

답안 #933441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933441 2024-02-25T16:55:44 Z themm1 Inside information (BOI21_servers) C++17
2.5 / 100
 220 ms 33160 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;
                for (int i = 0; i < N; i++) parents.pb(i);
                heights.assign(N, 1);
        }

        int find_set(int u) {
                if (parents[u] == u) 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 root_edge, 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))
                };
                if (next.u == 0) {
                        ups[u][i].last_edge = root_edge;
                        // dmpn(u); dmp(root_edge);
                }
                // dmpn(u); dmpn(next.u); dmpn(ups[u][i].incr); dmp(ups[u][i].decr);
                // cout << u << " -> " << next.u << "; incr: " << ups[u][i].incr << ", decr: " << ups[u][i].decr << endl;
        }

        for (auto [id, v] : adj[u]) {
                if (v != p) {
                        if (u == p) root_edge = id;
                        preprocess_dfs(v, u, time, root_edge, 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;
        int last_u = 0;
        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 || (next.first_edge > 0 && next.first_edge < last_u)) incr = false;
                        if (next.last_edge != 0) last_u = next.last_edge;
                }
        }
        // dmpn(u); dmpn(incr); dmp(mx);

        bool decr = true;
        int last_v = N + 1;
        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 || (next.first_edge > 0 && next.first_edge > last_v)) decr = false;
                        if (next.last_edge != 0) last_v = next.last_edge;
                }
        }
        // dmpn(v); dmpn(decr); dmp(mn);
        return incr && decr && last_u <= last_v;
}

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);
                        answers[query_idx] = -4;
                        query_idx++;
                }
        }
        int time = 0;
        preprocess_dfs(0, 0, time, 0);
        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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 142 ms 1692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 142 ms 1692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 1972 KB Output is correct
2 Correct 211 ms 25088 KB Output is correct
3 Correct 207 ms 25672 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 1972 KB Output is correct
2 Correct 211 ms 25088 KB Output is correct
3 Correct 207 ms 25672 KB Output is correct
4 Incorrect 151 ms 2760 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 1548 KB Output is correct
2 Incorrect 220 ms 33160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 1548 KB Output is correct
2 Incorrect 220 ms 33160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 1532 KB Output is correct
2 Incorrect 219 ms 23404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 1532 KB Output is correct
2 Incorrect 219 ms 23404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 1636 KB Output is correct
2 Incorrect 209 ms 33100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 1636 KB Output is correct
2 Incorrect 209 ms 33100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 140 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 140 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -