CODE FESTIVAL 2016 Final

Submission #1049361

Source codeソースコード

#include <cstdio>
#include<iostream>
#include <set>

using namespace std;

struct query
{
	int o,x,y,z;
	inline bool operator < (const query t) const
	{
		if (z!=t.z)
			return z<t.z;
		else
			if (x!=t.x)
				return x<t.x;
			else
				if (y!=t.y)
					return y<t.y;
				else
					return o<t.o;
	}
};

set <query> S;
query q[300000];
query t;

char c[6000000];
int f[300000];
int i,k,l,m,n,fx,fy;
long long s;
bool b;

inline int fastscanf()
{
	int t=0;
	l++;
	while (! ((c[l]>47) && (c[l]<58)))
		l++;
	while ((c[l]>47) && (c[l]<58))
		t=t*10+c[l]-48,l++;
	return t;
}

inline int getfather(int x)
{
	if (f[x]==x)
		return x;
	else
		return f[x]=getfather(f[x]);
}

int main()
{
	fread(c+1,1,5999999,stdin);
	n=fastscanf(),m=fastscanf();
	for (i=0;i<n;i++)
		f[i]=i;
	for (i=1;i<=m;i++)
	{
		q[i].x=fastscanf(),q[i].y=fastscanf(),q[i].z=fastscanf();
		S.insert(q[i]);
	}
	for (k=1;k<n;)
	{
		t=*S.begin(),b=false;
		S.erase(S.begin());
		fx=getfather(t.x);
		fy=getfather(t.y);
		if (fx!=fy)
		{
			b=true;
			s=s+t.z;
			f[fx]=fy;
			k++;
		}
		if (! t.o)
		{
			t.x++;
			if (t.x==n)
				t.x=0;
		}
		else
		{
			t.y++;
			if (t.y==n)
				t.y=0;
		}
		t.z++,t.o=t.o^1;
		fx=getfather(t.x);
		fy=getfather(t.y);
		if (fx!=fy)
			b=true;
		if (b)
			S.insert(t);
	}
	cout<<s<<endl;
}

Submission

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

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

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

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 1300 / 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 96 ms 18560 KB
01-03.txt AC 130 ms 21120 KB
01-04.txt AC 19 ms 1664 KB
01-05.txt AC 24 ms 1408 KB
01-06.txt AC 27 ms 1280 KB
01-07.txt AC 25 ms 1152 KB
01-08.txt AC 31 ms 1152 KB
01-09.txt AC 52 ms 2048 KB
01-10.txt AC 100 ms 11136 KB
01-11.txt AC 129 ms 20480 KB
01-12.txt AC 153 ms 21120 KB
01-13.txt AC 154 ms 21120 KB
01-14.txt AC 156 ms 21120 KB
01-15.txt AC 167 ms 21120 KB
01-16.txt AC 159 ms 21120 KB
01-17.txt AC 155 ms 21120 KB
01-18.txt AC 39 ms 8704 KB
01-19.txt AC 25 ms 1152 KB
01-20.txt AC 50 ms 1152 KB
01-21.txt AC 88 ms 6400 KB
01-22.txt AC 169 ms 19584 KB
01-23.txt AC 183 ms 19584 KB
01-24.txt AC 30 ms 2304 KB
01-25.txt AC 124 ms 21120 KB
01-26.txt AC 27 ms 1024 KB
01-27.txt AC 49 ms 1920 KB
01-28.txt AC 111 ms 13440 KB
01-29.txt AC 137 ms 20608 KB
01-30.txt AC 156 ms 21248 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB
sample-03.txt AC 3 ms 256 KB