Submission #3524358


Source Code Expand

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef double dd;
#define For(i,j,k) for (int i=(int)j;i<=(int)k;++i)
#define Forr(i,j,k) for (int i=(int)j;i>=(int)k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;

template<typename T>bool chkmax(T &a,T b) { return a<b?a=b,1:0; }
template<typename T>bool chkmin(T &a,T b) { return a>b?a=b,1:0; }

const int maxn=2e6+1e2;
const int inf=0x3f3f3f3f;
struct Edge {
	int from,to,dis;
	bool operator < (const Edge &aa) const {
		return dis<aa.dis;
	}
}e[maxn];
int n,m;
int tot;
ll Ans;
int fa[maxn],val[maxn];

inline int read() {
	int x=0,p=1;
	char c=getchar();
	while (!isdigit(c)) { if (c=='-') p=-1; c=getchar();}
	while (isdigit(c)) { x=(x<<1)+(x<<3)+(c-'0'); c=getchar();}
	return x*p;
}

inline void add(int u,int v,int w) {
	e[++tot]=(Edge){u,v,w};
}

int find(int x) {
	if (x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}

int main() {
	n=read(); m=read();
	For (i,0,n) fa[i]=i; Set(val,inf);
	while (m--) {
		int u=read(),v=read(),w=read(); u%=n; v%=n;
		chkmin(val[u],w+1); chkmin(val[v],w+2);
		add(u,v,w);
	}
	For (i,1,n<<1) chkmin(val[i%n],val[(i-1)%n]+2);
	For (i,0,n-1) add(i,(i+1)%n,val[i]);
	sort(e+1,e+tot+1);
	For (i,1,tot) {
		int u=e[i].from,v=e[i].to;
		u=find(u); v=find(v);
		if (u!=v) {
			Ans+=1ll*e[i].dis; fa[u]=v;
		}
	}
	printf("%lld\n",Ans);
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User Wuweizheng
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1478 Byte
Status AC
Exec Time 84 ms
Memory 19712 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 36
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 4 ms 10496 KB
01-02.txt AC 42 ms 12544 KB
01-03.txt AC 78 ms 16896 KB
01-04.txt AC 23 ms 16896 KB
01-05.txt AC 16 ms 15616 KB
01-06.txt AC 19 ms 16128 KB
01-07.txt AC 18 ms 14976 KB
01-08.txt AC 18 ms 14720 KB
01-09.txt AC 23 ms 14592 KB
01-10.txt AC 49 ms 16640 KB
01-11.txt AC 67 ms 16640 KB
01-12.txt AC 79 ms 16640 KB
01-13.txt AC 79 ms 16640 KB
01-14.txt AC 81 ms 16640 KB
01-15.txt AC 84 ms 16640 KB
01-16.txt AC 78 ms 16640 KB
01-17.txt AC 78 ms 16640 KB
01-18.txt AC 56 ms 19712 KB
01-19.txt AC 17 ms 14976 KB
01-20.txt AC 21 ms 14592 KB
01-21.txt AC 37 ms 16640 KB
01-22.txt AC 62 ms 16640 KB
01-23.txt AC 62 ms 16640 KB
01-24.txt AC 18 ms 17664 KB
01-25.txt AC 76 ms 19712 KB
01-26.txt AC 23 ms 17152 KB
01-27.txt AC 25 ms 16128 KB
01-28.txt AC 53 ms 18176 KB
01-29.txt AC 62 ms 17536 KB
01-30.txt AC 74 ms 18176 KB
sample-01.txt AC 4 ms 10496 KB
sample-02.txt AC 4 ms 10496 KB
sample-03.txt AC 4 ms 10496 KB