oj.uz

Submission #541332

# Submission time Handle Problem Language Result Execution time Memory
541332 2022-03-23T06:38:57 Z Stickfish Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 26752 KB 
#include <iostream>
#include <vector>
using namespace std;

struct way {
    int mnt = -177013;
    int mxt = -177013;
    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) {
        if (mnt == -177013)
            return w;
        if (w.mnt == -177013)
            return *this;
        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;
    }

    friend ostream& operator<<(ostream& o, way w) {
        o << "[" << w.incr << ' ' << w.dcr << ' ' << w.mnt << ' ' << w.mxt << "]";
        return o;
    }
};

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;
    //cout << "!" << v << ' ' << ans << '\n';
    while (d) {
        if (depth[v] - depth[crt[v].first] <= d) {
            //cout << "JOJO" << ' ' << crt[v].second << endl;
            ans = ans + crt[v].second;
            d -= depth[v] - depth[crt[v].first];
            v = crt[v].first;
        } else {
            //cout << "DIO" << endl;
            ans = ans + rt[v].second;
            --d;
            v = rt[v].first;
        }
        //cout << "?" << v << ' ' << ans << '\n';
    }
    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}});
        }
    }
    rt[0] = {0, -177013};
    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 {
            if (v == u) {
                cout << "yes\n";
                continue;
            }
            auto ans = lca(v, u);
            way w;
            if (v == ans.first)
                w = ans.second.second.reverse();
            else if (u == ans.first)
                w = ans.second.first;
            else
                w = ans.second.first + ans.second.second.reverse();
            //cout << "(" << v + 1 << ' ' << u + 1 << ' ' << ans.first + 1 << ") " << w.incr << ' ' << w.mnt << ' ' << w.mxt << ' ' << w.mnt << '\n';
            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 57 ms 6824 KB Output is correct
2 Correct 90 ms 6880 KB Output is correct
3 Correct 74 ms 7020 KB Output is correct
4 Correct 103 ms 7080 KB Output is correct
5 Correct 95 ms 7428 KB Output is correct
6 Correct 73 ms 7028 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6824 KB Output is correct
2 Correct 90 ms 6880 KB Output is correct
3 Correct 74 ms 7020 KB Output is correct
4 Correct 103 ms 7080 KB Output is correct
5 Correct 95 ms 7428 KB Output is correct
6 Correct 73 ms 7028 KB Output is correct
7 Correct 60 ms 6844 KB Output is correct
8 Correct 79 ms 6884 KB Output is correct
9 Correct 216 ms 7020 KB Output is correct
10 Correct 79 ms 6988 KB Output is correct
11 Correct 78 ms 7288 KB Output is correct
12 Correct 730 ms 6980 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6848 KB Output is correct
2 Correct 167 ms 12856 KB Output is correct
3 Correct 164 ms 15652 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6848 KB Output is correct
2 Correct 167 ms 12856 KB Output is correct
3 Correct 164 ms 15652 KB Output is correct
4 Correct 54 ms 7744 KB Output is correct
5 Execution timed out 3558 ms 15664 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6804 KB Output is correct
2 Correct 196 ms 23228 KB Output is correct
3 Correct 198 ms 23376 KB Output is correct
4 Correct 202 ms 23212 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6804 KB Output is correct
2 Correct 196 ms 23228 KB Output is correct
3 Correct 198 ms 23376 KB Output is correct
4 Correct 202 ms 23212 KB Output is correct
5 Correct 63 ms 7676 KB Output is correct
6 Correct 198 ms 26116 KB Output is correct
7 Execution timed out 3565 ms 26588 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6848 KB Output is correct
2 Correct 190 ms 12844 KB Output is correct
3 Correct 209 ms 16800 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6848 KB Output is correct
2 Correct 190 ms 12844 KB Output is correct
3 Correct 209 ms 16800 KB Output is correct
4 Correct 58 ms 7764 KB Output is correct
5 Execution timed out 3580 ms 15908 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6848 KB Output is correct
2 Correct 202 ms 23356 KB Output is correct
3 Correct 193 ms 23168 KB Output is correct
4 Correct 209 ms 23228 KB Output is correct
5 Correct 66 ms 7752 KB Output is correct
6 Correct 178 ms 16164 KB Output is correct
7 Correct 190 ms 16624 KB Output is correct
8 Correct 237 ms 17092 KB Output is correct
9 Correct 207 ms 16964 KB Output is correct
10 Correct 207 ms 22232 KB Output is correct
11 Correct 246 ms 21348 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6848 KB Output is correct
2 Correct 202 ms 23356 KB Output is correct
3 Correct 193 ms 23168 KB Output is correct
4 Correct 209 ms 23228 KB Output is correct
5 Correct 66 ms 7752 KB Output is correct
6 Correct 178 ms 16164 KB Output is correct
7 Correct 190 ms 16624 KB Output is correct
8 Correct 237 ms 17092 KB Output is correct
9 Correct 207 ms 16964 KB Output is correct
10 Correct 207 ms 22232 KB Output is correct
11 Correct 246 ms 21348 KB Output is correct
12 Correct 64 ms 7760 KB Output is correct
13 Correct 200 ms 26116 KB Output is correct
14 Execution timed out 3559 ms 26380 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6820 KB Output is correct
2 Correct 85 ms 6872 KB Output is correct
3 Correct 79 ms 7124 KB Output is correct
4 Correct 93 ms 7044 KB Output is correct
5 Correct 91 ms 7384 KB Output is correct
6 Correct 73 ms 6988 KB Output is correct
7 Correct 57 ms 6904 KB Output is correct
8 Correct 163 ms 12908 KB Output is correct
9 Correct 160 ms 15672 KB Output is correct
10 Correct 60 ms 7740 KB Output is correct
11 Correct 202 ms 26500 KB Output is correct
12 Correct 207 ms 26556 KB Output is correct
13 Correct 205 ms 26752 KB Output is correct
14 Correct 60 ms 7740 KB Output is correct
15 Correct 181 ms 16056 KB Output is correct
16 Correct 203 ms 16572 KB Output is correct
17 Correct 226 ms 17088 KB Output is correct
18 Correct 205 ms 16984 KB Output is correct
19 Correct 238 ms 22224 KB Output is correct
20 Correct 241 ms 21404 KB Output is correct
21 Correct 186 ms 16176 KB Output is correct
22 Correct 185 ms 16292 KB Output is correct
23 Correct 198 ms 16660 KB Output is correct
24 Correct 193 ms 16608 KB Output is correct
25 Correct 204 ms 18876 KB Output is correct
26 Correct 207 ms 16088 KB Output is correct
27 Correct 190 ms 16208 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6820 KB Output is correct
2 Correct 85 ms 6872 KB Output is correct
3 Correct 79 ms 7124 KB Output is correct
4 Correct 93 ms 7044 KB Output is correct
5 Correct 91 ms 7384 KB Output is correct
6 Correct 73 ms 6988 KB Output is correct
7 Correct 57 ms 6904 KB Output is correct
8 Correct 163 ms 12908 KB Output is correct
9 Correct 160 ms 15672 KB Output is correct
10 Correct 60 ms 7740 KB Output is correct
11 Correct 202 ms 26500 KB Output is correct
12 Correct 207 ms 26556 KB Output is correct
13 Correct 205 ms 26752 KB Output is correct
14 Correct 60 ms 7740 KB Output is correct
15 Correct 181 ms 16056 KB Output is correct
16 Correct 203 ms 16572 KB Output is correct
17 Correct 226 ms 17088 KB Output is correct
18 Correct 205 ms 16984 KB Output is correct
19 Correct 238 ms 22224 KB Output is correct
20 Correct 241 ms 21404 KB Output is correct
21 Correct 186 ms 16176 KB Output is correct
22 Correct 185 ms 16292 KB Output is correct
23 Correct 198 ms 16660 KB Output is correct
24 Correct 193 ms 16608 KB Output is correct
25 Correct 204 ms 18876 KB Output is correct
26 Correct 207 ms 16088 KB Output is correct
27 Correct 190 ms 16208 KB Output is correct
28 Correct 60 ms 7720 KB Output is correct
29 Correct 78 ms 7968 KB Output is correct
30 Correct 213 ms 8296 KB Output is correct
31 Correct 81 ms 8172 KB Output is correct
32 Correct 77 ms 8444 KB Output is correct
33 Correct 689 ms 8348 KB Output is correct
34 Correct 55 ms 7684 KB Output is correct
35 Execution timed out 3582 ms 15664 KB Time limit exceeded
36 Halted 0 ms 0 KB -