Submission #1261813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261813		anha3k25cvp	Potemkin cycle (CEOI15_indcyc)	C++20	70 / 100	1096 ms	1096 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;

class DynamicBitset {
private:
    uint64_t* data;
    int size_;
    int words_;
    static constexpr int BITS_PER_WORD = 64;

    static constexpr uint64_t ALL_ONES = ~0ULL;

    inline int word_index(int pos) const noexcept { return pos >> 6; }
    inline int bit_index(int pos) const noexcept { return pos & 63; }
    
    // Helper function for aligned allocation on Windows
    static uint64_t* allocate_aligned(size_t size) {
#ifdef _WIN32
        return static_cast<uint64_t*>(_aligned_malloc(size, 64));
#else
        return static_cast<uint64_t*>(aligned_alloc(64, size));
#endif
    }
    
    static void deallocate_aligned(uint64_t* ptr) {
#ifdef _WIN32
        _aligned_free(ptr);
#else
        free(ptr);
#endif
    }
    
public:
    // Constructor with memory alignment for better cache performance
    explicit DynamicBitset(int n) noexcept : size_(n) {
        words_ = (n + BITS_PER_WORD - 1) >> 6;
        data = allocate_aligned(words_ * sizeof(uint64_t));
        memset(data, 0, words_ * sizeof(uint64_t));
    }

    DynamicBitset(const DynamicBitset& other) noexcept 
        : size_(other.size_), words_(other.words_) {
        data = allocate_aligned(words_ * sizeof(uint64_t));
        memcpy(data, other.data, words_ * sizeof(uint64_t));
    }

    DynamicBitset(DynamicBitset&& other) noexcept 
        : data(other.data), size_(other.size_), words_(other.words_) {
        other.data = nullptr;
        other.size_ = 0;
        other.words_ = 0;
    }

    DynamicBitset& operator=(const DynamicBitset& other) noexcept {
        if (this != &other) {
            if (words_ != other.words_) {
                deallocate_aligned(data);
                words_ = other.words_;
                data = allocate_aligned(words_ * sizeof(uint64_t));
            }
            size_ = other.size_;
            memcpy(data, other.data, words_ * sizeof(uint64_t));
        }
        return *this;
    }
    
    DynamicBitset& operator=(DynamicBitset&& other) noexcept {
        if (this != &other) {
            deallocate_aligned(data);
            data = other.data;
            size_ = other.size_;
            words_ = other.words_;
            other.data = nullptr;
            other.size_ = 0;
            other.words_ = 0;
        }
        return *this;
    }
    
    ~DynamicBitset() { 
        deallocate_aligned(data); 
    }

    inline void set(int pos) noexcept {
        data[word_index(pos)] |= (1ULL << bit_index(pos));
    }
    
    inline void reset(int pos) noexcept {
        data[word_index(pos)] &= ~(1ULL << bit_index(pos));
    }
    
    inline void flip(int pos) noexcept {
        data[word_index(pos)] ^= (1ULL << bit_index(pos));
    }
    
    inline bool test(int pos) const noexcept {
        return (data[word_index(pos)] >> bit_index(pos)) & 1;
    }

    DynamicBitset operator&(const DynamicBitset& other) const noexcept {
        DynamicBitset result(size_);
        const int unroll_factor = 4;
        int i = 0;
    
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            result.data[i] = data[i] & other.data[i];
            result.data[i+1] = data[i+1] & other.data[i+1];
            result.data[i+2] = data[i+2] & other.data[i+2];
            result.data[i+3] = data[i+3] & other.data[i+3];
        }
    
        for (; i < words_; ++i) {
            result.data[i] = data[i] & other.data[i];
        }
        return result;
    }
    
    DynamicBitset operator|(const DynamicBitset& other) const noexcept {
        DynamicBitset result(size_);
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            result.data[i] = data[i] | other.data[i];
            result.data[i+1] = data[i+1] | other.data[i+1];
            result.data[i+2] = data[i+2] | other.data[i+2];
            result.data[i+3] = data[i+3] | other.data[i+3];
        }
        
        for (; i < words_; ++i) {
            result.data[i] = data[i] | other.data[i];
        }
        return result;
    }
    
    DynamicBitset operator^(const DynamicBitset& other) const noexcept {
        DynamicBitset result(size_);
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            result.data[i] = data[i] ^ other.data[i];
            result.data[i+1] = data[i+1] ^ other.data[i+1];
            result.data[i+2] = data[i+2] ^ other.data[i+2];
            result.data[i+3] = data[i+3] ^ other.data[i+3];
        }
        
        for (; i < words_; ++i) {
            result.data[i] = data[i] ^ other.data[i];
        }
        return result;
    }

    DynamicBitset& operator&=(const DynamicBitset& other) noexcept {
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            data[i] &= other.data[i];
            data[i+1] &= other.data[i+1];
            data[i+2] &= other.data[i+2];
            data[i+3] &= other.data[i+3];
        }
        
        for (; i < words_; ++i) {
            data[i] &= other.data[i];
        }
        return *this;
    }
    
    DynamicBitset& operator|=(const DynamicBitset& other) noexcept {
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            data[i] |= other.data[i];
            data[i+1] |= other.data[i+1];
            data[i+2] |= other.data[i+2];
            data[i+3] |= other.data[i+3];
        }
        
        for (; i < words_; ++i) {
            data[i] |= other.data[i];
        }
        return *this;
    }
    
    DynamicBitset& operator^=(const DynamicBitset& other) noexcept {
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            data[i] ^= other.data[i];
            data[i+1] ^= other.data[i+1];
            data[i+2] ^= other.data[i+2];
            data[i+3] ^= other.data[i+3];
        }
        
        for (; i < words_; ++i) {
            data[i] ^= other.data[i];
        }
        return *this;
    }

    inline int count() const noexcept {
        int cnt = 0;
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            cnt += __builtin_popcountll(data[i]);
            cnt += __builtin_popcountll(data[i+1]);
            cnt += __builtin_popcountll(data[i+2]);
            cnt += __builtin_popcountll(data[i+3]);
        }
        
        for (; i < words_; ++i) {
            cnt += __builtin_popcountll(data[i]);
        }
        return cnt;
    }

    inline bool any() const noexcept {
        const int unroll_factor = 4;
        int i = 0;
        
        for (; i <= words_ - unroll_factor; i += unroll_factor) {
            if (data[i] | data[i+1] | data[i+2] | data[i+3]) return true;
        }
        
        for (; i < words_; ++i) {
            if (data[i]) return true;
        }
        return false;
    }
    
    inline bool none() const noexcept { return !any(); }

    template<typename Func>
    inline void for_each_set_bit(Func&& func) const noexcept {
        for (int word_idx = 0; word_idx < words_; ++word_idx) {
            uint64_t word = data[word_idx];
            while (word) {
                int bit = __builtin_ctzll(word);
                func(word_idx * BITS_PER_WORD + bit);
                word &= word - 1;
            }
        }
    }

    vector<int> get_set_bits() const {
        vector<int> result;
        result.reserve(count());
        
        for (int word_idx = 0; word_idx < words_; ++word_idx) {
            uint64_t word = data[word_idx];
            while (word) {
                int bit = __builtin_ctzll(word);
                result.push_back(word_idx * BITS_PER_WORD + bit);
                word &= word - 1;
            }
        }
        return result;
    }

    inline int find_first() const noexcept {
        for (int i = 0; i < words_; ++i) {
            if (data[i]) {
                return i * BITS_PER_WORD + __builtin_ctzll(data[i]);
            }
        }
        return size_;
    }
    
    inline int find_next(int pos) const noexcept {
        if (++pos >= size_) return size_;
        
        int word_idx = word_index(pos);
        int bit_idx = bit_index(pos);

        uint64_t word = data[word_idx] & (~0ULL << bit_idx);
        if (word) {
            return word_idx * BITS_PER_WORD + __builtin_ctzll(word);
        }
    
        for (int i = word_idx + 1; i < words_; ++i) {
            if (data[i]) {
                return i * BITS_PER_WORD + __builtin_ctzll(data[i]);
            }
        }
        return size_;
    }
    
    inline int size() const noexcept { return size_; }
    inline void clear() noexcept { memset(data, 0, words_ * sizeof(uint64_t)); }
    
    inline bool operator[](int pos) const noexcept { return test(pos); }
    
    bool operator==(const DynamicBitset& other) const noexcept {
        if (size_ != other.size_) return false;
        return memcmp(data, other.data, words_ * sizeof(uint64_t)) == 0;
    }
    
    bool operator!=(const DynamicBitset& other) const noexcept {
        return !(*this == other);
    }
};

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 <DynamicBitset> connected(n + 1, DynamicBitset(n + 1));
    vector <Edge> e(m + 1);
    for (int i = 1; i <= m; i ++) {
        cin >> e[i].u >> e[i].v;
        connected[e[i].u].set(e[i].v);
        connected[e[i].v].set(e[i].u);
    }
    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;
        DynamicBitset mask(n + 1);
        for (int w = 1; w <= n; w ++)
            if (a[w])
                mask.set(w);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            DynamicBitset cur = mask & connected[u];
            // duyệt nhanh các bit 1 trong cur
            for (int v = cur.find_first(); v < cur.size(); 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.reset(v);
            }
        }
        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:328:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  328 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:329:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  329 |         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