Submission #720663

#	Time	Username	Problem	Language	Result	Execution time	Memory
720663		Johann	Inside information (BOI21_servers)	C++14	20 / 100	108 ms	11524 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvpii vector<vpii>
#define sz(x) (int)(x).size()

vi T;           // time to connect v to its parent
vi cntChildren; // times I am contained in my subtree (including me)
vvi cntSplit;   // [v][i] cntChildren v split up in what came from left (i = 0) and right (i = 1)

int lca(int a, int b)
{
    int h = 1;
    while (h <= a && h <= b)
        h <<= 1;
    while (a >= h)
        a >>= 1;
    while (b >= h)
        b >>= 1;
    while (a != b)
        a >>= 1, b >>= 1;
    return a;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;
    T.resize(N + 1, -1);
    cntChildren.assign(N + 1, 1); // er selbst
    cntSplit.assign(N + 1, vi(2, 0));
    for (int t = 1; t < N + K; ++t)
    {
        string command;
        cin >> command;
        if (command == "S")
        {
            int a, b;
            cin >> a >> b;
            if (b < a)
                swap(a, b);
            // a < b: a parent, b child
            T[b] = t;
            int v = b;
            int tt = t;
            while (v > 1 && T[v] != -1 && T[v] <= tt)
            {
                tt = T[v];
                int p = v / 2;
                ++cntChildren[p];
                ++cntSplit[p][v % 2];
                v = p;
            }
        }
        else if (command == "Q")
        {
            int a, d;
            cin >> a >> d; // whether a stores b
            int l = lca(a, d);

            bool poss = true;
            int ta = T[a];
            int v = a;
            while (poss && v > l)
            {
                if (ta != -1 && T[v] != -1 && T[v] <= ta)
                {
                    ta = T[v];
                    v >>= 1;
                }
                else
                    poss = false;
            }

            int td = T[d];
            v = d;
            while (poss && v > l)
            {
                if (td != -1 && T[v] != -1 && T[v] >= td)
                {
                    td = T[v];
                    v >>= 1;
                }
                else
                    poss = false;
            }

            if ((td <= ta || a == l || d == l) && poss)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else
        {
            int d;
            cin >> d; // number of servers to store d
            int cnt = cntChildren[d];

            int tt = T[d];
            int v = d;
            while (v > 1 && T[v] != -1 && T[v] >= tt)
            {
                int p = v / 2;
                ++cnt; // for node p
                tt = T[v];
                int other = (v + 1) % 2;
                if (2 * p + other <= N && T[2 * p + other] != -1 && T[2 * p + other] >= tt)
                    cnt += cntSplit[p][other];
                v = p;
            }

            cout << cnt << "\n";
            // fflush(stdout);
        }
    }
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5