oj.uz

Submission #619773

# Submission time Handle Problem Language Result Execution time Memory
619773 2022-08-02T15:40:37 Z yuto1115 Inside information (BOI21_servers) C++17
50 / 100
 187 ms 37984 KB 
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vvp G(n);
    vp es;
    vector qs(n, vector<tuple<int, int, int>>());
    rep(_, n + q - 1) {
        char c;
        cin >> c;
        if (c == 'S') {
            int a, b;
            cin >> a >> b;
            --a, --b;
            G[a].eb(b, SZ(es));
            G[b].eb(a, SZ(es));
            es.eb(a, b);
        } else if (c == 'Q') {
            int a, d;
            cin >> a >> d;
            --a, --d;
            qs[SZ(es)].eb(0, d, a);
        } else {
            int d;
            cin >> d;
            --d;
            qs[SZ(es)].eb(1, d, 0);
        }
    }
    vi dep(n);
    vvi par(20, vi(n));
    vi pid(n), inc(n), dec(n);
    auto dfs = [&](auto &dfs, int u, int p, int d, int _pid) -> void {
        dep[u] = d;
        par[0][u] = p;
        pid[u] = _pid;
        for (auto[v, id]: G[u]) {
            if (v == p) continue;
            inc[v] = (u and _pid > id ? inc[u] : 0) + 1;
            dec[v] = (u and _pid < id ? dec[u] : 0) + 1;
            dfs(dfs, v, u, d + 1, id);
        }
    };
    dfs(dfs, 0, -1, 0, -1);
    rep(k, 19) {
        rep(i, n) {
            if (par[k][i] == -1) par[k + 1][i] = -1;
            else par[k + 1][i] = par[k][par[k][i]];
        }
    }
    auto la = [&](int u, int d) {
        if (!d) return u;
        rep(k, 20) {
            if (d >> k & 1) {
                u = par[k][u];
                assert(u != -1);
            }
        }
        return u;
    };
    auto lca = [&](int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        v = la(v, dep[v] - dep[u]);
        if (u == v) return u;
        rrep(k, 20) {
            if (par[k][u] != par[k][v]) {
                u = par[k][u];
                v = par[k][v];
            }
        }
        return par[0][u];
    };
    vs ans(q);
    int it = 0;
    rep(i, n) {
        for (auto[t, d, a]: qs[i]) {
            if (t == 0) {
                int l = lca(d, a);
                int hd = dep[d] - dep[l];
                int ha = dep[a] - dep[l];
                int when;
                if (d == a) {
                    when = -1;
                } else if (l == d) {
                    when = (dec[a] >= ha ? pid[a] : inf);
                } else if (l == a) {
                    when = (inc[d] >= hd ? pid[la(d, hd - 1)] : inf);
                } else {
                    // d -> (edge : x) -> l -> (edge : y) -> a
                    int x = pid[la(d, hd - 1)];
                    int y = pid[la(a, ha - 1)];
                    when = (inc[d] >= hd and dec[a] >= ha and x < y ? pid[a] : inf);
                }
                ans[it] = (when < i ? "yes" : "no");
            } else {
            
            }
            ++it;
        }
    }
    rep(i, q) cout << ans[i] << '\n';
}

//4 4
//S 1 2
//S 1 3
//S 3 4
//Q 2 1
//Q 2 2
//Q 2 3
//Q 2 4

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6996 KB Output is correct
2 Correct 52 ms 8616 KB Output is correct
3 Correct 49 ms 8908 KB Output is correct
4 Correct 59 ms 8680 KB Output is correct
5 Correct 39 ms 8152 KB Output is correct
6 Correct 36 ms 8292 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6996 KB Output is correct
2 Correct 52 ms 8616 KB Output is correct
3 Correct 49 ms 8908 KB Output is correct
4 Correct 59 ms 8680 KB Output is correct
5 Correct 39 ms 8152 KB Output is correct
6 Correct 36 ms 8292 KB Output is correct
7 Incorrect 36 ms 6928 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 29 ms 6980 KB Output is correct
2 Correct 135 ms 33612 KB Output is correct
3 Correct 123 ms 33596 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6980 KB Output is correct
2 Correct 135 ms 33612 KB Output is correct
3 Correct 123 ms 33596 KB Output is correct
4 Incorrect 28 ms 7008 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 32 ms 6972 KB Output is correct
2 Correct 135 ms 37888 KB Output is correct
3 Correct 128 ms 37804 KB Output is correct
4 Correct 112 ms 37824 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6972 KB Output is correct
2 Correct 135 ms 37888 KB Output is correct
3 Correct 128 ms 37804 KB Output is correct
4 Correct 112 ms 37824 KB Output is correct
5 Incorrect 30 ms 6972 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 35 ms 6972 KB Output is correct
2 Correct 141 ms 32884 KB Output is correct
3 Correct 122 ms 32208 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6972 KB Output is correct
2 Correct 141 ms 32884 KB Output is correct
3 Correct 122 ms 32208 KB Output is correct
4 Incorrect 34 ms 6924 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 31 ms 7012 KB Output is correct
2 Correct 135 ms 37984 KB Output is correct
3 Correct 126 ms 37840 KB Output is correct
4 Correct 106 ms 37784 KB Output is correct
5 Correct 35 ms 6972 KB Output is correct
6 Correct 128 ms 32880 KB Output is correct
7 Correct 133 ms 32288 KB Output is correct
8 Correct 165 ms 32728 KB Output is correct
9 Correct 142 ms 34856 KB Output is correct
10 Correct 145 ms 35916 KB Output is correct
11 Correct 182 ms 35184 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7012 KB Output is correct
2 Correct 135 ms 37984 KB Output is correct
3 Correct 126 ms 37840 KB Output is correct
4 Correct 106 ms 37784 KB Output is correct
5 Correct 35 ms 6972 KB Output is correct
6 Correct 128 ms 32880 KB Output is correct
7 Correct 133 ms 32288 KB Output is correct
8 Correct 165 ms 32728 KB Output is correct
9 Correct 142 ms 34856 KB Output is correct
10 Correct 145 ms 35916 KB Output is correct
11 Correct 182 ms 35184 KB Output is correct
12 Incorrect 29 ms 7004 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 35 ms 6944 KB Output is correct
2 Correct 56 ms 8532 KB Output is correct
3 Correct 39 ms 8864 KB Output is correct
4 Correct 57 ms 8604 KB Output is correct
5 Correct 39 ms 8124 KB Output is correct
6 Correct 37 ms 8320 KB Output is correct
7 Correct 27 ms 6980 KB Output is correct
8 Correct 141 ms 33692 KB Output is correct
9 Correct 138 ms 33544 KB Output is correct
10 Correct 30 ms 6972 KB Output is correct
11 Correct 127 ms 37844 KB Output is correct
12 Correct 128 ms 37884 KB Output is correct
13 Correct 121 ms 37844 KB Output is correct
14 Correct 36 ms 6968 KB Output is correct
15 Correct 128 ms 32880 KB Output is correct
16 Correct 124 ms 32200 KB Output is correct
17 Correct 167 ms 32800 KB Output is correct
18 Correct 154 ms 34816 KB Output is correct
19 Correct 144 ms 35840 KB Output is correct
20 Correct 187 ms 35244 KB Output is correct
21 Correct 145 ms 34108 KB Output is correct
22 Correct 144 ms 34112 KB Output is correct
23 Correct 144 ms 34388 KB Output is correct
24 Correct 142 ms 34532 KB Output is correct
25 Correct 142 ms 35000 KB Output is correct
26 Correct 112 ms 32664 KB Output is correct
27 Correct 104 ms 32068 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6944 KB Output is correct
2 Correct 56 ms 8532 KB Output is correct
3 Correct 39 ms 8864 KB Output is correct
4 Correct 57 ms 8604 KB Output is correct
5 Correct 39 ms 8124 KB Output is correct
6 Correct 37 ms 8320 KB Output is correct
7 Correct 27 ms 6980 KB Output is correct
8 Correct 141 ms 33692 KB Output is correct
9 Correct 138 ms 33544 KB Output is correct
10 Correct 30 ms 6972 KB Output is correct
11 Correct 127 ms 37844 KB Output is correct
12 Correct 128 ms 37884 KB Output is correct
13 Correct 121 ms 37844 KB Output is correct
14 Correct 36 ms 6968 KB Output is correct
15 Correct 128 ms 32880 KB Output is correct
16 Correct 124 ms 32200 KB Output is correct
17 Correct 167 ms 32800 KB Output is correct
18 Correct 154 ms 34816 KB Output is correct
19 Correct 144 ms 35840 KB Output is correct
20 Correct 187 ms 35244 KB Output is correct
21 Correct 145 ms 34108 KB Output is correct
22 Correct 144 ms 34112 KB Output is correct
23 Correct 144 ms 34388 KB Output is correct
24 Correct 142 ms 34532 KB Output is correct
25 Correct 142 ms 35000 KB Output is correct
26 Correct 112 ms 32664 KB Output is correct
27 Correct 104 ms 32068 KB Output is correct
28 Incorrect 37 ms 6924 KB Extra information in the output file
29 Halted 0 ms 0 KB -