oj.uz

Submission #720663

# Submission time Handle Problem Language Result Execution time Memory
720663 2023-04-08T21:08:10 Z Johann Inside information (BOI21_servers) C++14
20 / 100
 108 ms 11524 KB 
#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

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 984 KB Output is correct
2 Correct 85 ms 11448 KB Output is correct
3 Correct 108 ms 11524 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 984 KB Output is correct
2 Correct 85 ms 11448 KB Output is correct
3 Correct 108 ms 11524 KB Output is correct
4 Correct 28 ms 1484 KB Output is correct
5 Correct 78 ms 11124 KB Output is correct
6 Correct 95 ms 11072 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 828 KB Output isn't correct
2 Halted 0 ms 0 KB -