Submission #1799800
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; 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; while (uf.getNumOfG() > 1) { Edge e = que.top(); que.pop(); if (!uf.sameSet(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 | 1372 Byte |
Status | TLE |
Exec Time | 2104 ms |
Memory | 9200 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 | 156 ms | 7792 KB |
01-03.txt | AC | 322 ms | 9072 KB |
01-04.txt | AC | 7 ms | 1024 KB |
01-05.txt | AC | 12 ms | 1024 KB |
01-06.txt | AC | 17 ms | 1024 KB |
01-07.txt | AC | 33 ms | 1024 KB |
01-08.txt | AC | 102 ms | 1024 KB |
01-09.txt | AC | 161 ms | 1600 KB |
01-10.txt | AC | 412 ms | 4212 KB |
01-11.txt | AC | 317 ms | 8432 KB |
01-12.txt | AC | 465 ms | 9200 KB |
01-13.txt | AC | 612 ms | 8560 KB |
01-14.txt | AC | 569 ms | 8816 KB |
01-15.txt | AC | 503 ms | 7664 KB |
01-16.txt | AC | 478 ms | 7536 KB |
01-17.txt | AC | 513 ms | 8304 KB |
01-18.txt | TLE | 2104 ms | 8560 KB |
01-19.txt | AC | 17 ms | 1024 KB |
01-20.txt | AC | 119 ms | 1152 KB |
01-21.txt | AC | 284 ms | 2680 KB |
01-22.txt | AC | 448 ms | 8944 KB |
01-23.txt | AC | 457 ms | 7280 KB |
01-24.txt | TLE | 2103 ms | 1600 KB |
01-25.txt | TLE | 2103 ms | 7920 KB |
01-26.txt | AC | 11 ms | 1024 KB |
01-27.txt | TLE | 2103 ms | 1600 KB |
01-28.txt | TLE | 2103 ms | 4212 KB |
01-29.txt | TLE | 2103 ms | 7664 KB |
01-30.txt | TLE | 2103 ms | 8176 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 |