Submission #732518

#	Time	Username	Problem	Language	Result	Execution time	Memory
732518		Programmer123	Through Another Maze Darkly (CCO21_day1problem3)	C++17	4 / 25	9092 ms	11884 KiB

Main

//Do initial DFSs to naively find first results.
//When return to root after N runs, all lasers should point to parent.
#include <bits/stdc++.h>
#define int long long int
#define init(x, s) x = new std::remove_pointer<decltype(x)>::type[s]
std::vector<int> traversal;
std::vector<int> *connections;
int *walkTime;
int *parent;
int *laserIndex;
bool *seen;
int traverse(int node) {
    walkTime[node] = 0;
    for (auto sub: connections[node]) {
        walkTime[node] += 2 + traverse(sub);
    }
    return walkTime[node];
}
int walk(int node, int steps) {
    if (steps == 0) return node;
    for (auto sub: connections[node]) {
        if (walkTime[sub] + 2 == steps) return node;
        if (walkTime[sub] + 2 <= steps) {
            steps -= walkTime[sub] + 2;
        } else {
            return walk(sub, steps - 1);
        }
    }
    assert(false);
}
signed main() {
    int N, Q;
    std::cin >> N >> Q;
    init(connections, N);
    init(walkTime, N);
    init(parent, N);
    init(laserIndex, N);
    init(seen, N);
    for (int i = 0; i < N; ++i) {
        seen[i] = false;
        laserIndex[i] = 0;
        int k;
        std::cin >> k;
        for (int j = 0; j < k; ++j) {
            int a;
            std::cin >> a;
            a--;
            connections[i].push_back(a);
        }
    }
    int answers[Q];
    typedef std::pair<int, int> qtp;//Value, index
    std::priority_queue<qtp, std::vector<qtp>, std::greater<>> queue;
    for (int i = 0; i < Q; ++i) {
        int x;
        std::cin >> x;
        queue.emplace(x, i);
    }
    int length = 0;
    int current = 0;
    int remaining = N;
    while ((current != 0 || remaining > 0) && !queue.empty()) {
        while ((!queue.empty()) && queue.top().first <= length) {
            answers[queue.top().second] = current;
            queue.pop();
        }
        if (!seen[current]) {
            seen[current] = true;
            remaining--;
        }
        laserIndex[current] = (laserIndex[current] + 1) % connections[current].size();
        //        traversal.push_back(current);
        current = connections[current][laserIndex[current]];
        length++;
    }
    if (!queue.empty()) {
        for (int i = 0; i < N; ++i) {
            std::vector<int> subtrees;
            int pIndex = laserIndex[i];
            for (int j = pIndex + 1; j < connections[i].size(); ++j) {
                subtrees.push_back(connections[i][j]);
            }
            for (int j = 0; j < pIndex; j++) {
                subtrees.push_back(connections[i][j]);
            }
            if (i == 0) subtrees.push_back(connections[i][laserIndex[i]]);
            connections[i] = subtrees;
        }
        traverse(0);
    }
    while (!queue.empty()) {
        int x = queue.top().first;
        int i = queue.top().second;
        queue.pop();
        std::cin >> x;
        x -= length;
        x = x % walkTime[0];
        answers[i] = walk(0, x);
    }
    for (int i = 0; i < Q; ++i) {
        std::cout << answers[i] + 1 << std::endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:80:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for (int j = pIndex + 1; j < connections[i].size(); ++j) {
      |                                      ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 12
• Subtask 4: 0 / 5