oj.uz

Submission #892022

# Submission time Handle Problem Language Result Execution time Memory
892022 2023-12-24T16:17:22 Z tengiz05 Through Another Maze Darkly (CCO21_day1problem3) C++17
0 / 25
 1405 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

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++) {
        int 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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 659244 KB Output is correct
2 Runtime error 1405 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -