oj.uz

Submission #541328

# Submission time Handle Problem Language Result Execution time Memory
541328 2022-03-23T06:14:52 Z Stickfish Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 26620 KB 
#include <iostream>
#include <vector>
using namespace std;

struct way {
    int mnt;
    int mxt;
    bool incr = true;
    bool dcr = true;
    
    way() {}

    way(int t): mnt(t), mxt(t) {}

    way reverse() {
        way ans;
        ans.mnt = mnt;
        ans.mxt = mxt;
        ans.dcr = incr;
        ans.incr = dcr;
        return ans;
    }

    way operator+(way w) {
        way ans;
        ans.mnt = min(mnt, w.mnt);
        ans.mxt = max(mxt, w.mxt);
        ans.incr = (incr && w.incr && mxt <= w.mnt);
        ans.dcr = (dcr && w.dcr && mnt >= w.mxt);
        return ans;
    }
};

const int MAXN = 120008;
vector<pair<int, int>> edg[MAXN];
int depth[MAXN];
pair<int, int> rt[MAXN];
pair<int, way> crt[MAXN];

void dfs(int v) {
    auto [rtv, tmv] = rt[v];
    int par = crt[rtv].first;
    int parpar = crt[par].first;
    if (depth[rtv] - depth[par] == depth[par] - depth[parpar]) {
        crt[v] = {parpar, way(tmv) + crt[rtv].second + crt[par].second};
    } else {
        crt[v] = {rtv, way(tmv)};
    }
    for (auto [u, t] : edg[v]) {
        if (u == rtv)
            continue;
        rt[u] = {v, t};
        depth[u] = depth[v] + 1;
        dfs(u);
    }
}

pair<int, way> lift(int v, int d) {
    way ans = rt[v].second;
    while (d) {
        if (depth[v] - depth[crt[v].first] <= d) {
            ans = ans + crt[v].second;
            d -= depth[v] - depth[crt[v].first];
            v = crt[v].first;
        } else {
            ans = ans + rt[v].second;
            --d;
            v = rt[v].first;
        }
    }
    return {v, ans};
}

pair<int, pair<way, way>> lca(int v, int u) {
    way ansv = rt[v].second;
    way ansu = rt[u].second;
    if (depth[v] > depth[u]) {
        pair<int, way> vlift = lift(v, depth[v] - depth[u]);
        ansv = ansv + vlift.second;
        v = vlift.first;
    } else if (depth[v] < depth[u]) {
        pair<int, way> ulift = lift(u, depth[u] - depth[v]);
        ansu = ansu + ulift.second;
        u = ulift.first;
    }
    while (u != v) {
        if (crt[v].first != crt[u].first) {
            ansv = ansv + crt[v].second;
            ansu = ansu + crt[u].second;
            v = crt[v].first;
            u = crt[u].first;
        } else {
            ansv = ansv + rt[v].second;
            ansu = ansu + rt[u].second;
            v = rt[v].first;
            u = rt[u].first;
        }
    }
    return {v, {ansv, ansu}};
}

bool ans_qr1(int v, int rt, int mnt, int mxt, int w) {
    if (v == w)
        return true;
    for (auto [u, t] : edg[v]) {
        if (u == rt)
            continue;
        if (t > mxt || t < mnt)
            continue;
        if (ans_qr1(u, v, t, mxt, w))
            return true;
    }
    return false;
}

int ans_qr2(int v, int rt, int mnt, int mxt) {
    int ans = 1;
    for (auto [u, t] : edg[v]) {
        if (u == rt)
            continue;
        if (t > mxt || t < mnt)
            continue;
        ans += ans_qr2(u, v, t, mxt);
    }
    return ans;
}

signed main() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, pair<int, int>>> qrs;
    for (int i = 0; i < n + k - 1; ++i) {
        char ch;
        cin >> ch;
        if (ch == 'S') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            edg[u].push_back({v, i});
            edg[v].push_back({u, i});
        } else if (ch == 'Q') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            qrs.push_back({i, {v, u}});
        } else {
            int v;
            cin >> v;
            --v;
            qrs.push_back({i, {v, -1}});
        }
    }
    dfs(0);
    for (int i = 0; i < k; ++i) {
        auto [t, qri] = qrs[i];
        auto [v, u] = qri;
        if (u == -1) {
            cout << ans_qr2(v, -1, 0, t) << '\n';
        } else {
            //auto ans = lca(v, u);
            //way w = ans.second.first + ans.second.second.reverse();
            //if (w.incr && w.mxt <= t) {
            if (ans_qr1(v, -1, 0, t, u)) {
                cout << "yes\n";
            } else {
                cout << "no\n";
            }
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6948 KB Output is correct
2 Correct 81 ms 8256 KB Output is correct
3 Correct 164 ms 8460 KB Output is correct
4 Correct 85 ms 8400 KB Output is correct
5 Correct 82 ms 8744 KB Output is correct
6 Correct 887 ms 8420 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6948 KB Output is correct
2 Correct 81 ms 8256 KB Output is correct
3 Correct 164 ms 8460 KB Output is correct
4 Correct 85 ms 8400 KB Output is correct
5 Correct 82 ms 8744 KB Output is correct
6 Correct 887 ms 8420 KB Output is correct
7 Correct 57 ms 7688 KB Output is correct
8 Correct 78 ms 8036 KB Output is correct
9 Correct 237 ms 8196 KB Output is correct
10 Correct 68 ms 8028 KB Output is correct
11 Correct 68 ms 8448 KB Output is correct
12 Correct 1106 ms 8296 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6864 KB Output is correct
2 Execution timed out 3567 ms 15632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6864 KB Output is correct
2 Execution timed out 3567 ms 15632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6804 KB Output is correct
2 Correct 212 ms 26556 KB Output is correct
3 Correct 197 ms 26548 KB Output is correct
4 Execution timed out 3560 ms 26620 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6804 KB Output is correct
2 Correct 212 ms 26556 KB Output is correct
3 Correct 197 ms 26548 KB Output is correct
4 Execution timed out 3560 ms 26620 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6864 KB Output is correct
2 Execution timed out 3572 ms 16316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6864 KB Output is correct
2 Execution timed out 3572 ms 16316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6808 KB Output is correct
2 Correct 194 ms 26588 KB Output is correct
3 Correct 200 ms 26508 KB Output is correct
4 Execution timed out 3574 ms 26556 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6808 KB Output is correct
2 Correct 194 ms 26588 KB Output is correct
3 Correct 200 ms 26508 KB Output is correct
4 Execution timed out 3574 ms 26556 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6844 KB Output is correct
2 Correct 86 ms 8260 KB Output is correct
3 Correct 157 ms 8376 KB Output is correct
4 Correct 79 ms 8468 KB Output is correct
5 Correct 78 ms 8776 KB Output is correct
6 Correct 894 ms 8504 KB Output is correct
7 Correct 58 ms 7772 KB Output is correct
8 Execution timed out 3570 ms 15728 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6844 KB Output is correct
2 Correct 86 ms 8260 KB Output is correct
3 Correct 157 ms 8376 KB Output is correct
4 Correct 79 ms 8468 KB Output is correct
5 Correct 78 ms 8776 KB Output is correct
6 Correct 894 ms 8504 KB Output is correct
7 Correct 58 ms 7772 KB Output is correct
8 Execution timed out 3570 ms 15728 KB Time limit exceeded
9 Halted 0 ms 0 KB -