Submission #666828

#	Time	Username	Problem	Language	Result	Execution time	Memory
666828		LFFB	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	642 ms	26464 KiB

ballmachine

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define debug(args...) //printf(args)
#define all(x) x.begin(),x.end()
typedef long long llong;

const int MAX_N = 1e5 + 10;
const int MAX_Q = 1e5 + 10;
const int LOG = 25;

int n, q;
int root;

int currentPointer = 0;
bool hasBall[MAX_N];

int parent[MAX_N];
std::vector<int> children[MAX_N];

bool marked[MAX_N];

void addChild(int x) {
    if (x == parent[x]) return;
    if (marked[x]) return;
    marked[x] = true;
    children[parent[x]].push_back(x);
    addChild(parent[x]);
}
void calculateChildren() {
    for (int i = 0; i < n; i++) {
        addChild(i);
    }
}

namespace Conversion {

    int currentLabel = 0;
    int label[MAX_N];
    int unlabel[MAX_N];
    int oldParent[MAX_N];
    std::vector<int> oldChildren[MAX_N];

    void calculateLabel(int node) {
        for (int child : children[node]) {
            calculateLabel(child);
        }
        label[node] = currentLabel;
        unlabel[currentLabel] = node;
        debug("relabling %d -> %d\n", node, currentLabel);
        currentLabel++;
    }

    void calculateLabels() {
        calculateLabel(root);
    }

    void relabel() {
        for (int i = 0; i < n; i++) {
            oldParent[i] = parent[i];
        }
        for (int i = 0; i < n; i++) {
            parent[label[i]] = label[oldParent[i]];
        }
        for (int i = 0; i < n; i++) {
            for (int child : children[i]) oldChildren[i].push_back(child);
        }
        for (int i = 0; i < n; i++) {
            children[label[i]].clear();
            for (int child : oldChildren[i]) children[label[i]].push_back(label[child]);
        }
    }

}

int superParent[MAX_N][LOG];
void setupBinaryLifting() {
    for (int i = 0; i < n; i++) {
        superParent[i][0] = parent[i];
    }
    superParent[root][0] = -1;
    for (int l = 1; l < LOG; l++) {
        for (int i = 0; i < n; i++) {
            if (superParent[i][l-1] == -1) superParent[i][l] = -1;
            else superParent[i][l] = superParent[ superParent[i][l-1] ][l-1];
        }
    }
}

void fallPointer() {
    for (int child : children[currentPointer]) {
        if (hasBall[child]) continue;
        debug("falling pointer from %d to %d\n", currentPointer, child);
        currentPointer = child;
        fallPointer();
        return;
    }
    debug("didnt fall pointer from %d\n", currentPointer);
}

int addBall() {
    debug("adding ball to %d\n", currentPointer);
    if (hasBall[currentPointer]) {
        printf("Something went wrong, tried to add ball to occupied spot(%d)\n", currentPointer);
        exit(1);
    }
    int answer = currentPointer;
    hasBall[currentPointer] = true;
    currentPointer = parent[currentPointer];
    fallPointer();
    return answer;
}

int addBalls(int x) {
    debug("adding %d balls\n", x);
    int answer;
    for (int i = 0; i < x; i++) answer = addBall();
    return answer;
}

int removeBall(int x) {
    debug("removing ball %d\n", x);
    if (!hasBall[x]) {
        printf("Something went wrong, trying to remove ball from empty spot %d\n", x);
        exit(1);
    }
    int count = 0;

    for (int l = LOG-1; l >= 0; l--) {
        int y = superParent[x][l];
        if (y == -1) continue;
        if (!hasBall[y]) continue;
        debug("changing %d to %d at l = %d\n", x, y, l);
        count += (1 << l);
        x = y;
    }

    hasBall[x] = false;
    if (x < currentPointer) currentPointer = x;
    debug("setting pointer to %d\n", currentPointer);
    return count;
}

int main() {

    scanf("%d %d", &n, &q);

    for (int i = 0; i < n; i++) {
        scanf("%d", &parent[i]);
        parent[i]--;
        if (parent[i] == -1) {
            parent[i] = i;
            root = i;
        }
    }

    calculateChildren();
    Conversion::calculateLabels();
    Conversion::relabel();
    root = Conversion::label[root];
    setupBinaryLifting();

    for (int query = 0; query < q; query++) {
        debug("----- query %d -----\n", query);
        int type, x;
        scanf("%d %d", &type, &x);
        if (type == 1) {
            int answer = addBalls(x);
            printf("%d\n", Conversion::unlabel[answer] + 1);
        } else if (type == 2) {
            int answer = removeBall(Conversion::label[x - 1]);
            printf("%d\n", answer);
        }
    }

}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         scanf("%d", &parent[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%d %d", &type, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int addBalls(int)':
ballmachine.cpp:121:12: warning: 'answer' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |     return answer;
      |            ^~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:172:54: warning: 'answer' may be used uninitialized in this function [-Wmaybe-uninitialized]
  172 |             printf("%d\n", Conversion::unlabel[answer] + 1);
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~^

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5