Submission #1635739
Source Code Expand
#include <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))
using namespace std;
template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}
using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// Problem Specific Parameter:
struct Union_find {
Union_find(int n) {par.resize(n), iota(_all(par), 0);}
int find(int x) {return (par[x] == x) ? x : par[x] = find(par[x]);}
void unite(int a, int b) {a = find(a), b = find(b); par[a] = b;}
bool same(int a, int b) {return find(a) == find(b);}
vector<int> par;
};
const int limit = 200010;
ll adj_cost[limit];
int main(void) {
int n, q;
cin >> n >> q;
const ll inf = 1LL << 40;
rep(i, n) adj_cost[i] = inf;
using edge = tuple<ll, ll, ll>;
vector<edge> graph;
rep(loop, q) {
ll a, b, c;
cin >> a >> b >> c;
chmin(adj_cost[a], c + 1);
chmin(adj_cost[b], c + 2);
graph.push_back(edge(c, a, b));
}
rep(i, 2 * n) chmin(adj_cost[i % n], adj_cost[(i + n - 1) % n] + 2LL);
rep(i,n) graph.push_back(edge(adj_cost[i],i,(i+1)%n));
sort(begin(graph),end(graph));
ll ans = 0LL;
Union_find uf(n);
for(auto &e:graph){
ll a,b,c;
tie(c,a,b) = e;
if(uf.same(a,b)) continue;
ans += c;
uf.unite(a,b);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
Hec |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
2278 Byte |
Status |
AC |
Exec Time |
263 ms |
Memory |
16108 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
1300 / 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 |
165 ms |
7920 KB |
01-03.txt |
AC |
249 ms |
14188 KB |
01-04.txt |
AC |
28 ms |
9072 KB |
01-05.txt |
AC |
19 ms |
9584 KB |
01-06.txt |
AC |
25 ms |
9196 KB |
01-07.txt |
AC |
23 ms |
9456 KB |
01-08.txt |
AC |
27 ms |
9840 KB |
01-09.txt |
AC |
40 ms |
10096 KB |
01-10.txt |
AC |
142 ms |
14316 KB |
01-11.txt |
AC |
230 ms |
13804 KB |
01-12.txt |
AC |
251 ms |
14188 KB |
01-13.txt |
AC |
254 ms |
15340 KB |
01-14.txt |
AC |
263 ms |
15980 KB |
01-15.txt |
AC |
254 ms |
15340 KB |
01-16.txt |
AC |
251 ms |
15468 KB |
01-17.txt |
AC |
251 ms |
14828 KB |
01-18.txt |
AC |
223 ms |
15336 KB |
01-19.txt |
AC |
23 ms |
10096 KB |
01-20.txt |
AC |
37 ms |
8944 KB |
01-21.txt |
AC |
91 ms |
8684 KB |
01-22.txt |
AC |
230 ms |
15084 KB |
01-23.txt |
AC |
217 ms |
16108 KB |
01-24.txt |
AC |
30 ms |
9456 KB |
01-25.txt |
AC |
245 ms |
14952 KB |
01-26.txt |
AC |
30 ms |
10220 KB |
01-27.txt |
AC |
42 ms |
8812 KB |
01-28.txt |
AC |
170 ms |
14316 KB |
01-29.txt |
AC |
236 ms |
14188 KB |
01-30.txt |
AC |
261 ms |
15212 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 |