oj.uz

Submission #933443

# Submission time Handle Problem Language Result Execution time Memory
933443 2024-02-25T16:58:40 Z themm1 Inside information (BOI21_servers) C++17
50 / 100
 432 ms 68860 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 = 20;
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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1616 KB Output is correct
2 Correct 151 ms 3200 KB Output is correct
3 Correct 177 ms 4444 KB Output is correct
4 Correct 151 ms 3224 KB Output is correct
5 Correct 183 ms 4868 KB Output is correct
6 Correct 189 ms 4424 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1616 KB Output is correct
2 Correct 151 ms 3200 KB Output is correct
3 Correct 177 ms 4444 KB Output is correct
4 Correct 151 ms 3224 KB Output is correct
5 Correct 183 ms 4868 KB Output is correct
6 Correct 189 ms 4424 KB Output is correct
7 Incorrect 147 ms 1880 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1912 KB Output is correct
2 Correct 308 ms 54848 KB Output is correct
3 Correct 313 ms 54684 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1912 KB Output is correct
2 Correct 308 ms 54848 KB Output is correct
3 Correct 313 ms 54684 KB Output is correct
4 Incorrect 159 ms 1924 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 1620 KB Output is correct
2 Correct 286 ms 65152 KB Output is correct
3 Correct 288 ms 65092 KB Output is correct
4 Correct 325 ms 67028 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 1620 KB Output is correct
2 Correct 286 ms 65152 KB Output is correct
3 Correct 288 ms 65092 KB Output is correct
4 Correct 325 ms 67028 KB Output is correct
5 Incorrect 142 ms 2384 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1704 KB Output is correct
2 Correct 294 ms 54848 KB Output is correct
3 Correct 288 ms 58620 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1704 KB Output is correct
2 Correct 294 ms 54848 KB Output is correct
3 Correct 288 ms 58620 KB Output is correct
4 Incorrect 147 ms 2384 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 1536 KB Output is correct
2 Correct 282 ms 65348 KB Output is correct
3 Correct 283 ms 65224 KB Output is correct
4 Correct 312 ms 66880 KB Output is correct
5 Correct 152 ms 2660 KB Output is correct
6 Correct 293 ms 58180 KB Output is correct
7 Correct 294 ms 58716 KB Output is correct
8 Correct 354 ms 59196 KB Output is correct
9 Correct 359 ms 59260 KB Output is correct
10 Correct 365 ms 64156 KB Output is correct
11 Correct 432 ms 63444 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 1536 KB Output is correct
2 Correct 282 ms 65348 KB Output is correct
3 Correct 283 ms 65224 KB Output is correct
4 Correct 312 ms 66880 KB Output is correct
5 Correct 152 ms 2660 KB Output is correct
6 Correct 293 ms 58180 KB Output is correct
7 Correct 294 ms 58716 KB Output is correct
8 Correct 354 ms 59196 KB Output is correct
9 Correct 359 ms 59260 KB Output is correct
10 Correct 365 ms 64156 KB Output is correct
11 Correct 432 ms 63444 KB Output is correct
12 Incorrect 142 ms 2388 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2212 KB Output is correct
2 Correct 148 ms 3120 KB Output is correct
3 Correct 174 ms 4440 KB Output is correct
4 Correct 145 ms 3104 KB Output is correct
5 Correct 177 ms 4864 KB Output is correct
6 Correct 188 ms 4400 KB Output is correct
7 Correct 153 ms 1908 KB Output is correct
8 Correct 311 ms 56432 KB Output is correct
9 Correct 312 ms 57664 KB Output is correct
10 Correct 149 ms 2388 KB Output is correct
11 Correct 288 ms 68516 KB Output is correct
12 Correct 301 ms 68860 KB Output is correct
13 Correct 312 ms 68368 KB Output is correct
14 Correct 147 ms 2644 KB Output is correct
15 Correct 293 ms 58012 KB Output is correct
16 Correct 288 ms 58436 KB Output is correct
17 Correct 357 ms 59168 KB Output is correct
18 Correct 354 ms 58900 KB Output is correct
19 Correct 347 ms 64064 KB Output is correct
20 Correct 417 ms 63616 KB Output is correct
21 Correct 327 ms 58128 KB Output is correct
22 Correct 327 ms 58488 KB Output is correct
23 Correct 327 ms 58332 KB Output is correct
24 Correct 330 ms 58692 KB Output is correct
25 Correct 347 ms 60972 KB Output is correct
26 Correct 295 ms 58108 KB Output is correct
27 Correct 273 ms 58428 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2212 KB Output is correct
2 Correct 148 ms 3120 KB Output is correct
3 Correct 174 ms 4440 KB Output is correct
4 Correct 145 ms 3104 KB Output is correct
5 Correct 177 ms 4864 KB Output is correct
6 Correct 188 ms 4400 KB Output is correct
7 Correct 153 ms 1908 KB Output is correct
8 Correct 311 ms 56432 KB Output is correct
9 Correct 312 ms 57664 KB Output is correct
10 Correct 149 ms 2388 KB Output is correct
11 Correct 288 ms 68516 KB Output is correct
12 Correct 301 ms 68860 KB Output is correct
13 Correct 312 ms 68368 KB Output is correct
14 Correct 147 ms 2644 KB Output is correct
15 Correct 293 ms 58012 KB Output is correct
16 Correct 288 ms 58436 KB Output is correct
17 Correct 357 ms 59168 KB Output is correct
18 Correct 354 ms 58900 KB Output is correct
19 Correct 347 ms 64064 KB Output is correct
20 Correct 417 ms 63616 KB Output is correct
21 Correct 327 ms 58128 KB Output is correct
22 Correct 327 ms 58488 KB Output is correct
23 Correct 327 ms 58332 KB Output is correct
24 Correct 330 ms 58692 KB Output is correct
25 Correct 347 ms 60972 KB Output is correct
26 Correct 295 ms 58108 KB Output is correct
27 Correct 273 ms 58428 KB Output is correct
28 Incorrect 145 ms 2484 KB Extra information in the output file
29 Halted 0 ms 0 KB -