Submission #3528202


Source Code Expand

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<<x<<endl
#define fi first
#define se second
#define mk make_pair
#define pb push_back
typedef long long ll;

using namespace std;

void File(){
	freopen("gkk.in","r",stdin);
	freopen("gkk.out","w",stdout);
}

template<typename T>void read(T &_){
	T __=0,mul=1; char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')mul=-1;
		ch=getchar();
	}
	while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
	_=__*mul;
}

const int maxn=2e5+10;
const int maxm=1e6+10;
int n,q,m;
ll f[maxn];
struct edge{
	int u,v;
	ll w;
	bool operator < (const edge & ano) const {
		return w<ano.w;
	}
}E[maxm];

namespace Kruskal{
	ll ans;
	int fa[maxn];
	int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
	void work(){
		REP(i,0,n-1)fa[i]=i;
		sort(E+1,E+m+1);
		REP(i,1,m){
			int u=E[i].u,v=E[i].v;
			if(find(u)==find(v))continue;
			fa[find(u)]=find(v);
			ans+=E[i].w;
		}
		printf("%lld\n",ans);
	}
}

int main(){
	//File();
	read(n); read(q);
	memset(f,63,sizeof(f));
	int u,v; ll w;
	REP(i,1,q){
		read(u),read(v),read(w);
		E[++m]=(edge){u,v,w};
		f[u]=min(f[u],w+1);
		f[v]=min(f[v],w+2);
	}
	REP(i,0,2*n-1){
		int pre= !(i%n) ? n-1 : i%n-1;
		f[i%n]=min(f[i%n],f[pre]+2);
	}
	REP(i,0,n-1){
		int nex=(i+1)%n;
		E[++m]=(edge){i,nex,f[i]};
	}
	Kruskal::work();
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User ylsoi
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1524 Byte
Status AC
Exec Time 79 ms
Memory 13056 KB

Compile Error

./Main.cpp: In function ‘void File()’:
./Main.cpp:15:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen("gkk.in","r",stdin);
                             ^
./Main.cpp:16:31: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen("gkk.out","w",stdout);
                               ^

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 2 ms 1792 KB
01-02.txt AC 42 ms 5120 KB
01-03.txt AC 77 ms 10240 KB
01-04.txt AC 22 ms 8192 KB
01-05.txt AC 14 ms 6912 KB
01-06.txt AC 18 ms 7424 KB
01-07.txt AC 17 ms 6272 KB
01-08.txt AC 17 ms 6016 KB
01-09.txt AC 21 ms 5888 KB
01-10.txt AC 48 ms 7936 KB
01-11.txt AC 65 ms 7552 KB
01-12.txt AC 78 ms 9984 KB
01-13.txt AC 77 ms 9984 KB
01-14.txt AC 78 ms 9984 KB
01-15.txt AC 79 ms 9984 KB
01-16.txt AC 77 ms 9984 KB
01-17.txt AC 77 ms 9984 KB
01-18.txt AC 57 ms 13056 KB
01-19.txt AC 17 ms 6272 KB
01-20.txt AC 21 ms 5888 KB
01-21.txt AC 36 ms 7936 KB
01-22.txt AC 61 ms 9984 KB
01-23.txt AC 61 ms 9984 KB
01-24.txt AC 17 ms 11008 KB
01-25.txt AC 77 ms 13056 KB
01-26.txt AC 22 ms 8576 KB
01-27.txt AC 23 ms 7424 KB
01-28.txt AC 52 ms 9472 KB
01-29.txt AC 61 ms 8448 KB
01-30.txt AC 72 ms 11520 KB
sample-01.txt AC 2 ms 1792 KB
sample-02.txt AC 2 ms 1792 KB
sample-03.txt AC 2 ms 1792 KB