CODE FESTIVAL 2016 Final

Submission #1049357

Source codeソースコード

#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

Task問題 G - Zigzag MST
User nameユーザ名 rxdoi
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 3064 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 0 / 1300 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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
01-10.txt WA
01-11.txt WA
01-12.txt WA
01-13.txt WA
01-14.txt WA
01-15.txt WA
01-16.txt WA
01-17.txt WA
01-18.txt AC 250 ms 125824 KB
01-19.txt AC 278 ms 118272 KB
01-20.txt WA
01-21.txt WA
01-22.txt WA
01-23.txt WA
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
01-28.txt TLE
01-29.txt TLE
01-30.txt TLE
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 2 ms 256 KB
sample-03.txt AC 3 ms 256 KB