oj.uz

답안 #892024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
892024 2023-12-24T16:35:22 Z tengiz05 Through Another Maze Darkly (CCO21_day1problem3) C++17
0 / 25
 1354 ms 1048576 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1028 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 13 ms 10704 KB Output is correct
4 Correct 2 ms 1628 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 3 ms 1884 KB Output is correct
7 Correct 4 ms 3300 KB Output is correct
8 Correct 10 ms 8412 KB Output is correct
9 Correct 32 ms 28072 KB Output is correct
10 Incorrect 61 ms 47744 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 940 ms 658480 KB Output is correct
2 Runtime error 1354 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1028 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -