Submission #1258140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258140		anha3k25cvp	Potemkin cycle (CEOI15_indcyc)	C++20	70 / 100	17 ms	1092 KiB

indcyc

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 1 + 3e2;
const int inf = 7 + 1e9;

struct Edge {
    int u, v;
};

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n, m;
    cin >> n >> m;
    vector <bitset <N>> connected(n + 1, 0);
    vector <Edge> e(m + 1);
    for (int i = 1; i <= m; i ++) {
        cin >> e[i].u >> e[i].v;
        connected[e[i].u][e[i].v] = connected[e[i].v][e[i].u] = 1;
    }
    for (int edge = 1; edge <= m; edge ++) {
        vector <int> a(n + 1, 1);
        for (int w = 1; w <= n; w ++)
            if (connected[e[edge].u][w] && connected[e[edge].v][w])
                a[w] = 0;
        vector <int> dp(n + 1, -1), tr(n + 1, 0);
        queue <int> q;
        q.push(e[edge].u);
        dp[e[edge].u] = 0;
        bitset <N> mask = 0;
        for (int w = 1; w <= n; w ++)
            mask[w] = a[w];
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            bitset <N> cur = mask & connected[u];
            // duyệt nhanh các bit 1 trong cur
            for (int v = cur._Find_first(); v < N; v = cur._Find_next(v)) {
                if (u == e[edge].u && v == e[edge].v)
                    continue;
                q.push(v);
                dp[v] = dp[u] + 1;
                tr[v] = u;
                mask[v] = 0;
            }
        }
        if (dp[e[edge].v] > 0) {
            int v = e[edge].v;
            cout << v << ' ';
            while (v != e[edge].u) {
                cout << tr[v] << ' ';
                v = tr[v];
            }
            return 0;
        }
    }
    cout << "no";
    return 0;
}


// #include <bits/stdc++.h>
// #define ll long long
// #define ull unsigned long long
// #define dl double
// #define st first
// #define nd second
// #define II pair <int, int>

// using namespace std;

// const int N = 1 + 1e3;
// const int inf = 7 + 1e9;

// struct Edge {
//     int u, v;
// };

// int s = -1, t = -1;
// vector <Edge> e;
// vector <int> deg, vis, p;
// vector <vector <int>> adj;

// void dfs(int u) {
//     if (s >= 0)
//         return;
//     vis[u] = 1;
//     for (int v : adj[u]) {
//         if (!vis[v]) {
//             p[v] = u;
//             // cout << "- " << u << ' ' << v << '\n';
//             dfs(v);
//         }
//         else if (s < 0 && vis[v] == 1) {
//             s = u;
//             t = v;
//         }
//         if (s >= 0)
//             return;
//     }
//     vis[u] = 2;
// }

// int main() {
// #define TASKNAME ""
//     ios_base :: sync_with_stdio (0);
//     cin.tie (0);
//     if ( fopen( TASKNAME".inp", "r" ) ) {
//         freopen (TASKNAME".inp", "r", stdin);
//         freopen (TASKNAME".out", "w", stdout);
//     }
//     int n, m; 
//     cin >> n >> m;
//     e.resize(2 * m + 2);
//     vector <vector <int>> f(n + 1, vector <int> (n + 1, 0));
//     for (int i = 1; i <= m; i ++) {
//         cin >> e[i].u >> e[i].v;
//         f[e[i].u][e[i].v] = i * 2;
//         f[e[i].v][e[i].u] = i * 2 + 1;
//     }
//     adj.resize(2 * m + 2);
//     for (int i = 1; i <= m; i ++) {
//         int u = e[i].u, v = e[i].v;
//         for (int w = 1; w <= n; w ++)
//             if (w != u && w != v) {
//                 if (f[v][w] && !f[u][w])
//                     adj[i * 2].push_back(f[v][w]);
//                 if (f[u][w] && !f[v][w])
//                     adj[i * 2 + 1].push_back(f[u][w]);
//             }
//     }
//     for (int i = m; i > 0; i --) {
//         e[i * 2] = e[i];
//         e[i * 2 + 1] = {e[i].v, e[i].u};
//     }
//     vis.assign(2 * m + 2, 0);
//     p.assign(2 * m + 2, 0);
//     for (int i = 2; i < m * 2 + 2; i ++)
//         if (!vis[i]) {
//             p[i] = 0;
//             dfs(i);
//             if (s >= 0)
//                 break;
//         }
//     if (s < 0) {
//         cout << "no";
//         return 0;
//     }
//     vector <int> c;
//     c.push_back(e[s].u);
//     while (s != t) {
//         s = p[s];
//         c.push_back(e[s].u);
//     }
//     for (int i = (int)c.size() - 1; i >= 0; i --)
//         for (int j = i + 3; j < c.size(); j ++)
//             if (f[c[i]][c[j]]) {
//                 for (int u = i; u <= j; u ++)
//                     cout << c[u] << ' ';
//                 return 0;
//             }
//     return 0;
// }

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:23:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:24:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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