Submission #1049357


Source Code Expand

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<iostream>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define For(i,x,y) for(int i=((int)x);i<=((int)y);i++)
#define Dep(i,y,x) for(int i=((int)y);i>=((int)x);i--)
#define Rep(i,x) for (int y,i=head[x];i;i=E[i].nxt)
using namespace std;

const int N=200005;
const int inf=1000000009;

typedef double db;
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pii;

/*inline int rd() {
	char c=getchar(); int t=0,f=1;
	while (c<48) c=getchar();
	while (c>47) t=(t<<1)+(t<<3)+c-48,c=getchar(); return t*f;
}*/
char Buf[30000000],*c=Buf;

inline int rd() {
	int t=0;
	while (*c<48) c++;
	while (*c>47) t=(t<<1)+(t<<3)+*c-48,c++; return t;
}
void wt(int x) {
	if (x<0) putchar('-'),wt(-x);
	else { if (x>9) wt(x/10); putchar(x%10+48); }
}

struct Data {
	int A,B,val,k;
	bool operator>(Data P)const {
		return val>P.val;
	}
}TP,tmp;

struct Priority_Queue {
	int size;
	Data Heap[N<<1];	
	Data top() { return Heap[1]; }
	inline void down() {
		int x=1,k=1;
		while (1) {
			if ((x<<1)<=size && Heap[k]>Heap[x<<1]) k=x<<1;
			if ((x<<1|1)<=size && Heap[k]>Heap[x<<1|1]) k=x<<1|1;
			if (x==k) return; swap(Heap[x],Heap[k]); x=k;
		}
	}
	inline void up(int x) {
		while (x>1) {
			if (Heap[x>>1]>Heap[x])
				swap(Heap[x>>1],Heap[x]),x>>=1;
			else return;
		}
	}
	inline void pop() { swap(Heap[1],Heap[size--]); down(); }
	inline void push(Data P) { Heap[++size]=P; up(size); }
}Q;

struct Hash_Table {
	bool key[60000007][2];
	inline int f(Data P) { return (1ll*P.A*500009%60000007+P.B)%60000007; }
	inline void ins(Data P) { key[f(P)][P.k]=1; swap(P.A,P.B),P.k^=1; key[f(P)][P.k]=1; return; }
	inline bool find(Data P) { if (key[f(P)][P.k]) return 1; swap(P.A,P.B),P.k^=1; return key[f(P)][P.k]; }
}Hash;

//priority_queue<Data>Q;
int n,m,fa[N],key; ll Ans;
//map<pair<pii,int>,bool>Map;

inline int get(int x) { return fa[x]==x?x:fa[x]=get(fa[x]); }

inline void inc(Data &P) {
	if (P.k==0) P.k=1,P.A++;
	else P.k=0,P.B++; P.val++;
	if (P.A==n) P.A=0;
	if (P.B==n) P.B=0; return;
}

int main() {
	fread(Buf,1,29999999,stdin);
	n=rd(),m=rd(); int cnt=0; tmp.k=0;
	For (i,1,m) {
		tmp.A=rd(),tmp.B=rd(),tmp.val=rd();
		Q.push(tmp);
	}
		
	For (i,0,n-1) fa[i]=i;
	while (Q.size) {
		if (key==n-1) break;
		TP=Q.top(),Q.pop();
		
		cnt++;
//		if (Map.find(mp(mp(TP.A,TP.B),TP.k))!=Map.end()) continue; else Map[mp(mp(TP.A,TP.B),TP.k)]=1;
//		if (Map.find(mp(mp(TP.B,TP.A),TP.k^1))!=Map.end()) continue; else Map[mp(mp(TP.B,TP.A),TP.k^1)]=1;
		if (Hash.find(TP)) continue; else Hash.ins(TP);
		
		if (get(TP.A)!=get(TP.B)) {
			Ans+=TP.val,key++;
			fa[get(TP.A)]=get(TP.B);
		}
//		else continue;
		inc(TP),Q.push(TP);
	}
	cout<<Ans<<endl;
//	printf("%d\n",cnt);
	return 0;
}
/*
7 1
5 2 1

*/

Submission Info

Submission Time
Task G - Zigzag MST
User rxdoi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3064 Byte
Status WA
Exec Time 2114 ms
Memory 125824 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:99:29: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  fread(Buf,1,29999999,stdin);
                             ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 16
WA × 13
TLE × 4
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
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 256 KB
01-02.txt AC 13 ms 6144 KB
01-03.txt AC 401 ms 125824 KB
01-04.txt AC 234 ms 118912 KB
01-05.txt AC 258 ms 118528 KB
01-06.txt AC 268 ms 118400 KB
01-07.txt AC 285 ms 118272 KB
01-08.txt AC 388 ms 118272 KB
01-09.txt WA 451 ms 118656 KB
01-10.txt WA 568 ms 121984 KB
01-11.txt WA 353 ms 125184 KB
01-12.txt WA 508 ms 125824 KB
01-13.txt WA 657 ms 125824 KB
01-14.txt WA 604 ms 125824 KB
01-15.txt WA 537 ms 125824 KB
01-16.txt WA 511 ms 125824 KB
01-17.txt WA 531 ms 125824 KB
01-18.txt AC 250 ms 125824 KB
01-19.txt AC 278 ms 118272 KB
01-20.txt WA 609 ms 118272 KB
01-21.txt WA 651 ms 119936 KB
01-22.txt WA 665 ms 124288 KB
01-23.txt WA 785 ms 124288 KB
01-24.txt AC 241 ms 118656 KB
01-25.txt AC 326 ms 125824 KB
01-26.txt AC 243 ms 118272 KB
01-27.txt TLE 2114 ms 118528 KB
01-28.txt TLE 2114 ms 123008 KB
01-29.txt TLE 2114 ms 125312 KB
01-30.txt TLE 2114 ms 125824 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 2 ms 256 KB
sample-03.txt AC 3 ms 256 KB