結果

問題 No.408 五輪ピック
ユーザー dontwannacry
提出日時 2025-04-25 22:13:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 322 ms / 5,000 ms
コード長 1,349 bytes
コンパイル時間 2,088 ms
コンパイル使用メモリ 197,428 KB
実行使用メモリ 54,148 KB
最終ジャッジ日時 2025-04-25 22:13:35
合計ジャッジ時間 5,241 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int N,M,A[20010],val[20010][3],cnt[20010];
bool vis[20010];
vector<int>ne[20010];
bitset<20010>mp[20010];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("circle.in","r",stdin);
    // freopen("circle.out","w",stdout);
    cin >> N >> M;
	for(int i = 1;i <= M;++i){
		int u,v;cin >> u >> v;
		ne[u].push_back(v);
		ne[v].push_back(u);
	}
	for(int v:ne[1]){vis[v] = 1;}
	for(int i = 2;i <= N;++i){
		for(int v:ne[i]){
			mp[i][v] = 1;
			if(vis[v]){
				if(val[i][1]){val[i][2] = val[i][1];}
				if(val[i][0]){val[i][1] = val[i][0];}
				val[i][0] = v;
			}
		}
		for(int k = 2;k >= 0;--k){if(val[i][k]){cnt[i] = k+1;break;}}
	}
	for(int i = 2;i < N;++i){
		for(int j = i+1;j <= N;++j){
			if(!mp[i][j]){continue;}
			if(cnt[i] == 0||cnt[j] == 0){continue;}
			if(cnt[i] == 1&&val[i][0] == j){continue;}
			if(cnt[j] == 1&&val[j][0] == i){continue;}
			if(cnt[i] == 3||cnt[j] == 3){cout << "YES\n";return 0;}
			int avi1 = 2,avi2 = 2;
			if(val[i][0] == j){avi1 = 1;}if(cnt[i] == 1||val[i][1] == j){avi1 -= 2;}
			if(val[j][0] == i){avi2 = 1;}if(cnt[j] == 1||val[j][1] == j){avi2 -= 2;}
			if(avi1 == -1||avi2 == -1){continue;}
			if(avi1 == 2||avi2 == 2||val[i][avi1] != val[j][avi2]){cout << "YES\n";return 0;}
		}
	}
	cout << "NO\n";
	return 0;
}
0