Submission #892024

#	Time	Username	Problem	Language	Result	Execution time	Memory
892024		tengiz05	Through Another Maze Darkly (CCO21_day1problem3)	C++17	0 / 25	1354 ms	1048576 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> e(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        e[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> e[i][j];
            e[i][j]--;
        }
    }
    
    vector<int> par(n, -1);
    vector<int> euler;
    function<void(int, int)> dfs = [&](int u, int p) {
        par[u] = p;
        euler.push_back(u);
        int k = e[u].size();
        if (p == -1) {
            for (int j = 0; j < k; j++) {
                int v = e[u][(1 + j) % k];
                dfs(v, u);
                euler.push_back(u);
            }
        } else {
            int f = 0;
            for (int j = 0; j < k; j++) {
                if (e[u][j] == p) {
                    f = j;
                }
            }
            f++;
            for (int j = 0; j < k - 1; j++) {
                int v = e[u][(f + j) % k];
                assert(v != p);
                dfs(v, u);
                euler.push_back(u);
            }
        }
    };
    dfs(0, -1);
    euler.pop_back();
    
    int cnt = 0;
    par[0] = e[0][0];
    vector<int> cur(n);
    for (int i = 0; i < n; i++) {
        cnt += par[i] == e[i][cur[i]];
    }
    vector<int> firstPart;
    
    function<void(int)> dfs2 = [&](int u) {
        firstPart.push_back(u);
        if (cnt == n) {
            return;
        }
        cnt -= par[u] == e[u][cur[u]];
        cur[u] = (cur[u] + 1) % e[u].size();
        cnt += par[u] == e[u][cur[u]];
        dfs2(e[u][cur[u]]);
        return;
    };
    dfs2(0);
    
    firstPart.pop_back();
    for (int i = 0; i < m; i++) {
        i64 K;
        cin >> K;
        if (K < firstPart.size()) {
            cout << firstPart[K] + 1 << "\n";
        } else {
            cout << euler[(K - firstPart.size()) % euler.size()] + 1 << "\n";
        }
    }
    
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:81:15: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         if (K < firstPart.size()) {
      |             ~~^~~~~~~~~~~~~~~~~~

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