Submission #1224575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224575		sokratisi	Inside information (BOI21_servers)	C++20	10 / 100	67 ms	1748 KiB

servers

#include <bits/stdc++.h>

using namespace std;

int n, q, a, b;
char c;
int child[2][125000];
vector<int> brep[2];

void bi_rep(int i, int a) {
    while (a) {
        brep[i].push_back(a%2);
        a/=2;
    }
    reverse(brep[i].begin(), brep[i].end());
}

int main() {
    scanf("%d%d", &n, &q);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        child[0][i] = INT_MAX;
        child[1][i] = INT_MAX;
    }
    for (int i = 0; i < n + q - 1; i++) {
        scanf("%c", &c); scanf("%c", &c);
        if (c == 'S') {
            scanf("%d%d", &a, &b);
            if (a > b) swap(a, b);
            if (b % 2 == 1) child[1][a] = cnt++;
            else child[0][a] = cnt++;
        }
        else if (c == 'Q') {
            scanf("%d%d", &a, &b); // has b traveled to a??
            // route from b to a has to be increasing
            brep[0].clear(); brep[1].clear();
            bi_rep(0, a); bi_rep(1, b);
            // for (auto u: brep[0]) printf("%d", u);
            // printf("\n");


            int ind = -1;
            int cur = 0;
            for (int i = 0; i < min(brep[0].size(), brep[1].size()); i++) {
                if (brep[0][i] == brep[1][i]) {
                    cur *= 2;
                    cur += brep[0][i];
                    ind = i;
                }
                else break;
            }
            // printf("%d\n", cur);
            int lst = -1;
            bool okay = true;
            int curcop = cur;
            // first loop is from lca to a, has to be inceasing
            for (int i = ind+1; i < brep[0].size(); i++) {
                // printf("%d ", child[brep[0][i]][curcop]);
                if (child[brep[0][i]][curcop] == INT_MAX || child[brep[0][i]][curcop]<lst) okay = false;
                lst = child[brep[0][i]][curcop];
                curcop *= 2;
                curcop += brep[0][i];
            }
            lst = INT_MAX;
            if (ind + 1 < brep[0].size()) {
                lst = child[brep[0][ind+1]][cur];
            }
            curcop = cur;
            for (int i = ind+1; i < brep[1].size(); i++) {
                if (child[brep[1][i]][curcop] == INT_MAX || child[brep[1][i]][curcop] > lst) okay = false;
                lst = child[brep[1][i]][curcop];
                curcop *= 2;
                curcop += brep[1][i];
            }
            if (okay) printf("yes\n");
            else printf("no\n");
        }


    }
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
servers.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%c", &c); scanf("%c", &c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%c", &c); scanf("%c", &c);
      |                          ~~~~~^~~~~~~~~~
servers.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |             scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
servers.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |             scanf("%d%d", &a, &b); // has b traveled to a??
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18