Submission #732494

#	Time	Username	Problem	Language	Result	Execution time	Memory
732494		Programmer123	Through Another Maze Darkly (CCO21_day1problem3)	C++17	4 / 25	3081 ms	1048576 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 current = 0;
    int remaining = N;
    while (current != 0 || remaining > 0) {
        if (!seen[current]) {
            seen[current] = true;
            remaining--;
        }
        laserIndex[current] = (laserIndex[current] + 1) % connections[current].size();
        traversal.push_back(current);
        current = connections[current][laserIndex[current]];
    }
#ifdef LOCAL
    for (auto n: traversal) {
        std::cout << n + 1 << " ";
    }
    std::cout << std::endl;
#endif
    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);
    for (int i = 0; i < Q; ++i) {
        int x;
        std::cin >> x;
        if (x < traversal.size()) {
            std::cout << traversal[x] + 1 << std::endl;
        } else {
            x -= traversal.size();
            x = x % walkTime[0];
            std::cout << walk(0, x) + 1 << std::endl;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:71:36: 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]
   71 |         for (int j = pIndex + 1; j < connections[i].size(); ++j) {
      |                                  ~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:84:15: 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]
   84 |         if (x < traversal.size()) {
      |             ~~^~~~~~~~~~~~~~~~~~

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