提出 #43433400

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Side
{
	int to;
	int next_side;
};
struct Fdlks
{
	Side sds[800012];
	int first[400012];
	int m;
	void init()
	{
		m=0;
		memset(sds,0,sizeof sds);
		memset(first,-1,sizeof first);
		for(int i=0;i<=800011;i++)
			sds[i].next_side=-1;
	}
	void add(int from,int to)
	{
		m++;
		sds[m].to=to;
		sds[m].next_side=first[from];
		first[from]=m;
	}
}fdlks;
bool h[400012];
int de[400012];
bool alr[400012];
bool dfs(int x,int d,int y)
{
	if(!y) alr[x]=true;
	if(de[x]!=-1&&de[x]%2!=d%2&&y==1) return true;
	if(y>=2) return false;
	if(de[x]!=-1) return false;
	de[x]=d;
	int ii=fdlks.first[x];
	while(ii!=-1)
	{
		if(dfs(fdlks.sds[ii].to,d+1,y+(h[x]==h[fdlks.sds[ii].to]))) return true;
		ii=fdlks.sds[ii].next_side;
	}
	de[x]=-1;
	return false;
}
signed main()
{
	memset(de,-1,sizeof de);
	int n,m;
	cin>>n>>m;
	fdlks.init();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		fdlks.add(x,y);
		fdlks.add(y,x);
	}
	for(int i=1;i<=n;i++)
		cin>>h[i];
	for(int i=1;i<=n;i++)
	{
		if(!alr[i]&&dfs(i,1,0))
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

提出情報

提出日時
問題 B - Switching Travel
ユーザ L3_035966
言語 C++ (GCC 9.2.1)
得点 500
コード長 1208 Byte
結果 AC
実行時間 1230 ms
メモリ 35184 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 2
AC × 46
セット名 テストケース
Sample sample-01.txt, sample-02.txt
All in-01.txt, in-02.txt, in-03.txt, in-04.txt, in-05.txt, in-06.txt, in-07.txt, in-08.txt, in-09.txt, in-10.txt, in-11.txt, in-12.txt, in-13.txt, in-14.txt, in-15.txt, in-16.txt, in-17.txt, in-18.txt, in-19.txt, in-20.txt, in-21.txt, in-22.txt, in-23.txt, in-24.txt, in-25.txt, in-26.txt, in-27.txt, in-28.txt, in-29.txt, in-30.txt, in-31.txt, in-32.txt, in-33.txt, in-34.txt, in-35.txt, in-36.txt, in-37.txt, in-38.txt, in-39.txt, in-40.txt, in-41.txt, in-42.txt, in-43.txt, in-44.txt, sample-01.txt, sample-02.txt
ケース名 結果 実行時間 メモリ
in-01.txt AC 136 ms 35184 KiB
in-02.txt AC 135 ms 35132 KiB
in-03.txt AC 130 ms 34932 KiB
in-04.txt AC 138 ms 35116 KiB
in-05.txt AC 138 ms 35064 KiB
in-06.txt AC 102 ms 22452 KiB
in-07.txt AC 116 ms 22508 KiB
in-08.txt AC 84 ms 22332 KiB
in-09.txt AC 83 ms 22344 KiB
in-10.txt AC 46 ms 22348 KiB
in-11.txt AC 99 ms 22412 KiB
in-12.txt AC 72 ms 22404 KiB
in-13.txt AC 154 ms 22580 KiB
in-14.txt AC 102 ms 22428 KiB
in-15.txt AC 65 ms 22412 KiB
in-16.txt AC 44 ms 22208 KiB
in-17.txt AC 104 ms 22508 KiB
in-18.txt AC 27 ms 22272 KiB
in-19.txt AC 90 ms 22320 KiB
in-20.txt AC 72 ms 22404 KiB
in-21.txt AC 83 ms 22304 KiB
in-22.txt AC 70 ms 22196 KiB
in-23.txt AC 122 ms 22272 KiB
in-24.txt AC 35 ms 22272 KiB
in-25.txt AC 105 ms 22376 KiB
in-26.txt AC 232 ms 22464 KiB
in-27.txt AC 119 ms 22456 KiB
in-28.txt AC 25 ms 22304 KiB
in-29.txt AC 29 ms 22252 KiB
in-30.txt AC 114 ms 22456 KiB
in-31.txt AC 327 ms 22500 KiB
in-32.txt AC 47 ms 22328 KiB
in-33.txt AC 59 ms 22236 KiB
in-34.txt AC 94 ms 22424 KiB
in-35.txt AC 328 ms 22576 KiB
in-36.txt AC 17 ms 22256 KiB
in-37.txt AC 19 ms 22276 KiB
in-38.txt AC 18 ms 22236 KiB
in-39.txt AC 18 ms 22240 KiB
in-40.txt AC 1230 ms 22172 KiB
in-41.txt AC 60 ms 22280 KiB
in-42.txt AC 141 ms 34992 KiB
in-43.txt AC 141 ms 34992 KiB
in-44.txt AC 136 ms 35116 KiB
sample-01.txt AC 18 ms 22280 KiB
sample-02.txt AC 23 ms 22252 KiB