結果

問題 No.408 五輪ピック
ユーザー FF256grhy
提出日時 2016-08-06 01:22:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,496 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 24,320 KB
実行使用メモリ 8,740 KB
最終ジャッジ日時 2024-11-07 01:45:38
合計ジャッジ時間 11,423 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
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];

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];
	}
	
	sort(0, m);
	
	bool flag = false;
	for(int i = 0; i < m; i++) { if( ! (e(0, a[i]) || e(0, b[i])) ) { continue; }
	for(int j = 0; j < m; 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(
			( e(0, a[i]) && e(0, a[j]) && e(b[i], b[j]) ) ||
			( e(0, a[i]) && e(0, b[j]) && e(b[i], a[j]) ) ||
			( e(0, b[i]) && e(0, a[j]) && e(a[i], b[j]) ) ||
			( e(0, b[i]) && e(0, b[j]) && e(a[i], a[j]) )
		) {
			flag = true;
			i = j = m;
		}
	}
	}
	
	printf("%s\n", flag ? "YES" : "NO");
	
	return 0;
}
0