Submission #5017910


Source Code Expand

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
using std::cin;
using std::cout;
using LL = long long;
using pii = std::pair<int, int>;
using pip = std::pair<int, pii>;
const int MAXN = 2e5 + 10;

int f[MAXN];

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)return false;
    f[fx] = fy;
    return true;
}

template<>
struct std::hash<pii> {
	size_t operator()(const pii &s) const {
		size_t out = 14695981039346656037ULL;
		static constexpr size_t mul = 1099511628211ULL;
		out = (out ^ s.first) * mul;
		out = (out ^ s.second) * mul;
		return out;
	}
};

void solve() {
    int n, m;
    cin >> n >> m;
    std::priority_queue<pip, std::vector<pip>, std::greater<>> q;
    for (int i = 1; i <= n; ++i) f[i] = i;

    for (int i = 0, A, B, C; i < m; ++i) {
        cin >> A >> B >> C;
        q.push({C, {A, B}});
    }

    int cnt = 0;
    LL ans = 0;
    std::unordered_set<pii> S;
    while (cnt != n - 1) {
        pip p = q.top();
        q.pop();
        int c = p.fi, a = p.se.fi, b = p.se.se;
        // cout << a << " " << b <<"\n";
        if (S.find({a, b}) != end(S)) continue;
        S.insert({a, b});
        if (unite(a, b)) ans += c, cnt++;
        q.push({c + 1, {b, (a + 1) % n}});
    }
    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef trote
    freopen("../1.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User vjudge2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1582 Byte
Status CE

Compile Error

./Main.cpp:26:13: error: specialization of ‘template<class _Tp> struct std::hash’ in different namespace [-fpermissive]
 struct std::hash<pii> {
             ^
In file included from /usr/include/c++/5/bits/basic_string.h:5556:0,
                 from /usr/include/c++/5/string:52,
                 from /usr/include/c++/5/bits/locale_classes.h:40,
                 from /usr/include/c++/5/bits/ios_base.h:41,
                 from /usr/include/c++/5/ios:42,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from /usr/include/c++/5/complex:45,
                 from /usr/include/c++/5/ccomplex:38,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52,
                 from ./Main.cpp:1:
/usr/include/c++/5/bits/functional_hash.h:58:12: error:   from definition of ‘template<class _Tp> struct std::hash’ [-fpermissive]
     struct hash;
            ^