Submission #2200973
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 200000
#define rint register int
#define gc() getchar()
inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}
struct E{int u,v,w; E(){} E(int _u, int _v, int _w){u=_u,v=_v,w=_w;}}; inline bool operator < (E a, E b){return a.w<b.w;}
int fa[MAXN+5], a[MAXN+5], n, c; long long Ans; vector<E> Ed; inline int getf(int x){return x^fa[x]?fa[x]=getf(fa[x]):x;}
inline bool Union(int x, int y){return (x=getf(x))^(y=getf(y))?fa[x]=y,true:false;}
int main()
{
for(rint q = (n = read(), memset(a,0x3f,n<<2), read()), A, B, C; q--; Ed.push_back(E(A,B,C)))
A = read(), B = read(), C = read(), a[B] = min(a[B],C+2), a[A] = min(a[A],C+1);
for(rint i = 0; i < (n<<1); a[-~i%n] = min(a[-~i%n],a[i%n]+2), i++);
for(rint i = 0; i < n; Ed.push_back(E(i,-~i%n,a[i])), fa[i] = i, i++); sort(Ed.begin(),Ed.end());
c = n-1; for(auto _:Ed)if(Union(_.u,_.v)&&(Ans+=_.w,!--c))break; printf("%lld\n",Ans); return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
vjudge1 |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
1124 Byte |
Status |
AC |
Exec Time |
74 ms |
Memory |
9584 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 |
38 ms |
4212 KB |
01-03.txt |
AC |
71 ms |
7536 KB |
01-04.txt |
AC |
21 ms |
5616 KB |
01-05.txt |
AC |
14 ms |
5492 KB |
01-06.txt |
AC |
18 ms |
5232 KB |
01-07.txt |
AC |
16 ms |
5364 KB |
01-08.txt |
AC |
17 ms |
5876 KB |
01-09.txt |
AC |
21 ms |
4724 KB |
01-10.txt |
AC |
46 ms |
8816 KB |
01-11.txt |
AC |
62 ms |
7536 KB |
01-12.txt |
AC |
73 ms |
8304 KB |
01-13.txt |
AC |
72 ms |
8688 KB |
01-14.txt |
AC |
74 ms |
7664 KB |
01-15.txt |
AC |
74 ms |
7920 KB |
01-16.txt |
AC |
72 ms |
8560 KB |
01-17.txt |
AC |
72 ms |
7664 KB |
01-18.txt |
AC |
55 ms |
8560 KB |
01-19.txt |
AC |
16 ms |
5364 KB |
01-20.txt |
AC |
20 ms |
4724 KB |
01-21.txt |
AC |
34 ms |
4976 KB |
01-22.txt |
AC |
58 ms |
7792 KB |
01-23.txt |
AC |
58 ms |
7792 KB |
01-24.txt |
AC |
14 ms |
5620 KB |
01-25.txt |
AC |
72 ms |
9584 KB |
01-26.txt |
AC |
20 ms |
4724 KB |
01-27.txt |
AC |
23 ms |
4724 KB |
01-28.txt |
AC |
49 ms |
8048 KB |
01-29.txt |
AC |
60 ms |
7536 KB |
01-30.txt |
AC |
70 ms |
7920 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 |