CODE FESTIVAL 2016 Final (Parallel)

Submission #1331335

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
int ace[222222],n;
priority_queue<pair<int,pair<int,int> > > q;
int ancestor(int x){
	return x-ace[x]?ace[x]=ancestor(ace[x]):x;
}
int main(){
	int m;
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++)
		ace[i] = i;
	while(m--){
		int A,B,C;
		scanf("%d%d%d",&A,&B,&C);
		q.push(make_pair(-C,make_pair(A,B)));
		q.push(make_pair(-(C+1),make_pair(B,(A+1)%n)));
	}
	long long int res = 0;
	while(!q.empty()){
		pair<int,pair<int,int> > pr = q.top();
		q.pop();
		int C = -pr.first, A = pr.second.first, B = pr.second.second;
		if(ancestor(A) == ancestor(B))
			continue;
		res += C;
		q.push(make_pair(-(C+2),make_pair((A+1)%n,(B+1)%n)));
		ace[ancestor(A)] = ancestor(B);
	}
	cout << res << endl;
	return 0;
}

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:15:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&A,&B,&C);
^

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,sample-01.txt,sample-02.txt,sample-03.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 118 ms 7024 KB
01-03.txt AC 151 ms 7920 KB
01-04.txt AC 8 ms 3328 KB
01-05.txt AC 8 ms 2048 KB
01-06.txt AC 11 ms 1664 KB
01-07.txt AC 12 ms 1280 KB
01-08.txt AC 21 ms 1152 KB
01-09.txt AC 38 ms 1600 KB
01-10.txt AC 106 ms 4212 KB
01-11.txt AC 149 ms 7664 KB
01-12.txt AC 172 ms 8560 KB
01-13.txt AC 176 ms 8176 KB
01-14.txt AC 172 ms 8560 KB
01-15.txt AC 174 ms 7664 KB
01-16.txt AC 172 ms 8688 KB
01-17.txt AC 175 ms 8304 KB
01-18.txt AC 96 ms 8940 KB
01-19.txt AC 10 ms 1280 KB
01-20.txt AC 34 ms 1152 KB
01-21.txt AC 90 ms 2680 KB
01-22.txt AC 198 ms 8688 KB
01-23.txt AC 195 ms 8304 KB
01-24.txt AC 14 ms 4604 KB
01-25.txt AC 128 ms 9580 KB
01-26.txt AC 8 ms 2688 KB
01-27.txt AC 35 ms 1600 KB
01-28.txt AC 128 ms 4212 KB
01-29.txt AC 162 ms 8688 KB
01-30.txt AC 183 ms 9328 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB