Submission #541328

#	Time	Username	Problem	Language	Result	Execution time	Memory
541328		Stickfish	Inside information (BOI21_servers)	C++17	5 / 100	3574 ms	26620 KiB

servers

#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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5