Submission #1799804
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define for_(i,a,b) for(int i=(a);i<(b);++i) typedef long long lint; typedef pair< int, int > pii; template< typename T > using Vec = vector< T >; class UnionFind { private: Vec< int > data; int num_of_g; public: UnionFind(int n) : data(n, -1), num_of_g(n) {} bool unionSet(int x, int y) { x = root(x); y = root(y); if (x == y) return 0; if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; --num_of_g; return 1; } bool sameSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } int getNumOfG() { return num_of_g; } }; struct Edge { int u, v; lint c; bool flag; bool operator > (const Edge& e) const { return c > e.c; } }; int main() { int N, Q; cin >> N >> Q; UnionFind uf(N); priority_queue< Edge, Vec< Edge >, greater< Edge > > que; for_(i,0,Q) { int A, B; lint C; cin >> A >> B >> C; que.push(Edge{A, B, C, true}); } lint ans = 0; set< pii > zigzag_set; while (uf.getNumOfG() > 1) { Edge e = que.top(); que.pop(); if (zigzag_set.count(pii(e.u, e.v))) continue; if (!uf.sameSet(e.u, e.v)) { zigzag_set.insert(pii(e.u, e.v)); uf.unionSet(e.u, e.v); ans += e.c; } if (e.flag) que.push(Edge{(e.u+1)%N, e.v, e.c+1, false}); else que.push(Edge{e.u, (e.v+1)%N, e.c+1, true}); } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | tsukasa_diary |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1516 Byte |
Status | TLE |
Exec Time | 2104 ms |
Memory | 16492 KB |
Judge Result
Set Name | sample | all | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1300 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
all | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 152 ms | 8432 KB |
01-03.txt | AC | 478 ms | 15084 KB |
01-04.txt | AC | 122 ms | 10368 KB |
01-05.txt | AC | 139 ms | 10368 KB |
01-06.txt | AC | 104 ms | 10368 KB |
01-07.txt | AC | 145 ms | 10368 KB |
01-08.txt | AC | 420 ms | 10368 KB |
01-09.txt | AC | 639 ms | 10620 KB |
01-10.txt | AC | 1268 ms | 12784 KB |
01-11.txt | AC | 569 ms | 10732 KB |
01-12.txt | AC | 1126 ms | 15084 KB |
01-13.txt | AC | 1646 ms | 15340 KB |
01-14.txt | AC | 1482 ms | 15084 KB |
01-15.txt | AC | 1257 ms | 15212 KB |
01-16.txt | AC | 1164 ms | 15724 KB |
01-17.txt | AC | 1226 ms | 15084 KB |
01-18.txt | AC | 370 ms | 15724 KB |
01-19.txt | AC | 107 ms | 10368 KB |
01-20.txt | AC | 638 ms | 10496 KB |
01-21.txt | AC | 1263 ms | 11764 KB |
01-22.txt | AC | 1409 ms | 15724 KB |
01-23.txt | AC | 1520 ms | 15212 KB |
01-24.txt | AC | 162 ms | 10748 KB |
01-25.txt | AC | 447 ms | 16492 KB |
01-26.txt | AC | 151 ms | 10368 KB |
01-27.txt | TLE | 2103 ms | 6012 KB |
01-28.txt | TLE | 2103 ms | 8560 KB |
01-29.txt | TLE | 2104 ms | 8944 KB |
01-30.txt | TLE | 2104 ms | 11372 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 1 ms | 256 KB |