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; ^