Submission #2949195

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m;

struct bigint {
    unsigned int x[16];
    bigint() {
        for (int i = 0; i < 16; ++i) x[i] = 0;
    }
    void operator|=(const bigint &p) {
        for (int i = 0; i < 16; ++i) {
            x[i] |= p.x[i];
        }
    }
    void set(int i) {
        x[i >> 5] |= (1u << (i & 31));
    }
    int get(int i) {
        return (x[i >> 5] >> (i & 31)) & 1;
    }
    bool operator==(const bigint &p) const {
        for (int i = 0; i < 16; ++i) if (x[i] != p.x[i]) return 0;
        return 1;
    }
} es[500], edge[64][1 << 8];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b; --a; --b;
        es[a].set(b);
	}
	
	for (int i = 0; i < 64; ++i) {
        for (int j = 0; j < (1 << 8); ++j) {
            for (int k = 0; k < 8; ++k) {
                if ((j >> k) & 1) {
                    edge[i][j] |= es[i << 3 | k];
                }
            }
        }
	}
	
	bigint st, tp, ed, zr;
	st.set(0);
	for (int i = 0; i < n; ++i) ed.set(i);
	for (int it = 0; it < n * n + 2; ++it) {
        if (st == ed) {
            printf("%d\n", it);
            return 0;
        }
        for (int i = 0; i < 64; ++i) {
            int x = 0;
            for (int j = 0; j < 8; ++j) {
                if (st.get(i << 3 | j)) x |= (1 << j);
            }
            tp |= edge[i][x];
        }
        st = tp;
        tp = zr;
	}
	printf("-1\n");
	return 0;
}

Submission Info

Judge Result