結果

問題 No.408 五輪ピック
ユーザー FF256grhyFF256grhy
提出日時 2016-08-06 01:39:49
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,616 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 24,064 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-11-07 01:53:23
合計ジャッジ時間 7,584 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 0 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 14 ms
5,248 KB
testcase_06 AC 10 ms
5,248 KB
testcase_07 AC 17 ms
5,248 KB
testcase_08 AC 10 ms
5,248 KB
testcase_09 AC 10 ms
5,248 KB
testcase_10 AC 10 ms
5,248 KB
testcase_11 AC 10 ms
5,248 KB
testcase_12 AC 18 ms
5,248 KB
testcase_13 AC 14 ms
5,248 KB
testcase_14 AC 4 ms
5,248 KB
testcase_15 AC 14 ms
5,248 KB
testcase_16 AC 14 ms
5,248 KB
testcase_17 AC 15 ms
5,248 KB
testcase_18 AC 15 ms
5,248 KB
testcase_19 AC 16 ms
5,248 KB
testcase_20 AC 4 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 7 ms
5,248 KB
testcase_23 AC 15 ms
5,248 KB
testcase_24 TLE -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:47:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:49:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |                 scanf("%d%d", &a[i], &b[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>

int n, m, a[50000], b[50000], c[50000], g[20000];

int d[50000];
void sort(int l, int r) {
	if(r - l < 2) { return; }
	
	int mm = (l + r) / 2;
	sort(l, mm);
	sort(mm, r);
	
	int ll = l, rr = mm, dd = l;
	while(dd < r) {
		bool flag;
		if(rr == r) { flag = true; }
		else if(ll == mm) { flag = false; }
		else { flag = (c[ll] <= c[rr]); }
		
		if(flag) { d[dd++] = c[ll++]; }
		else     { d[dd++] = c[rr++]; }
	}
	
	for(dd = l; dd < r; dd++) { c[dd] = d[dd]; }
	
	return;
}

bool f(int x, int y) {
	int z = x * 20000 + y;
	
	int l = 0, r = m, mm;
	while(r - l > 1) {
		mm = (l + r) / 2;
		if(c[mm] <= z) { l = mm; }
		else { r = mm; }
	}
	
	return (c[l] == z);
}

bool e(int x, int y) {
	return ( f(x, y) || f(y, x) );
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		a[i]--; b[i]--;
		c[i] = a[i] * 20000 + b[i];
		if(a[i] == 0) { g[ b[i] ] = 1; }
		if(b[i] == 0) { g[ a[i] ] = 1; }
	}
	
	sort(0, m);
	
	bool flag = false;
	for(int i = 0; i < m; i++) { if( ! (g[ a[i] ] == 1 || g[ b[i] ] == 1) ) { continue; }
	for(int j = 0; j < i; j++) {
		if(
			a[i] == 0    || b[i] == 0    || a[j] == 0    || b[j] == 0    ||
			a[i] == a[j] || a[i] == b[j] || b[i] == a[j] || b[i] == b[j]
		) { continue; }
		
		if(
			( g[ a[i] ] == 1 && g[ a[j] ] == 1 && e(b[i], b[j]) ) ||
			( g[ a[i] ] == 1 && g[ b[j] ] == 1 && e(b[i], a[j]) ) ||
			( g[ b[i] ] == 1 && g[ a[j] ] == 1 && e(a[i], b[j]) ) ||
			( g[ b[i] ] == 1 && g[ b[j] ] == 1 && e(a[i], a[j]) )
		) {
			flag = true;
			i = j = m;
		}
	}
	}
	
	printf("%s\n", flag ? "YES" : "NO");
	
	return 0;
}
0