Submission #1049354

---

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>

#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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:122:1: error: ‘cout’ was not declared in this scope
 cout<<Ans<<endl;
 ^
./Main.cpp:122:12: error: ‘endl’ was not declared in this scope
 cout<<Ans<<endl;
            ^
./Main.cpp:98: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);
                             ^