Submission #1325038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325038		mduc209	Potemkin cycle (CEOI15_indcyc)	C++20	20 / 100	1095 ms	1988 KiB

indcyc

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1005; // Để dư dả cho cả mảng
int N, R;
bool is_adj[MAXN][MAXN];
vector<int> adj[MAXN];

int visited[MAXN];
int parent_node[MAXN];
int step_cnt = 0; // Kỹ thuật reset mảng O(1)

void solve() {
    for (int u = 1; u <= N; ++u) {
        for (int v : adj[u]) {
            ++step_cnt; // Tương đương với việc reset toàn bộ mảng visited
            
            // Chặn đỉnh u và chặn các đỉnh kề với u CÓ NỐI trực tiếp với v
            visited[u] = step_cnt;
            visited[v] = step_cnt;
            for (int x : adj[u]) {
                if (is_adj[v][x]) {
                    visited[x] = step_cnt;
                }
            }

            queue<int> q;
            q.push(v);
            parent_node[v] = -1;
            
            int target_w = -1;

            while (!q.empty()) {
                int curr = q.front();
                q.pop();
                
                // Nếu chạm tới một đỉnh kề của u (mà không bị chặn), đây chính là w
                if (curr != v && is_adj[u][curr]) {
                    target_w = curr;
                    break;
                }
                
                for (int nxt : adj[curr]) {
                    if (visited[nxt] != step_cnt) {
                        visited[nxt] = step_cnt;
                        parent_node[nxt] = curr;
                        q.push(nxt);
                    }
                }
            }
            
            // Nếu tìm thấy chu trình, truy vết và in ra
            if (target_w != -1) {
                vector<int> path;
                path.push_back(u);
                
                int curr = target_w;
                while (curr != -1) {
                    path.push_back(curr);
                    curr = parent_node[curr];
                }
                
                for (size_t k = 0; k < path.size(); ++k) {
                    cout << path[k] << (k + 1 == path.size() ? "" : " ");
                }
                cout << "\n";
                return;
            }
        }
    }
    cout << "NO\n";
}

int main() {
    // Tối ưu tốc độ đọc ghi I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (cin >> N >> R) {
        for (int i = 0; i < R; ++i) {
            int u, v;
            cin >> u >> v;
            is_adj[u][v] = is_adj[v][u] = true;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10