Submission #1607392


Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}
namespace fucker
{
	typedef long long ll;
	const int N=100100,M=N*2;
	int begin[N],next[M],to[M],w[M];
	int col[N];
	int n,m,e;
	ll ans;
	void add(int x,int y,int z=1,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		w[e]=z;
		if(k)add(y,x,2,0);
	}
	void initialize()
	{
		read(n),read(m);
		for(int u,v;m--;)
			read(u),read(v),add(u,v);
	}
	int cnt[3],tmp;
	bool dfs(int p)
	{
		cnt[col[p]]++;

		bool ret=1;
		for(int i=begin[p],q;i;i=next[i])
		{
			q=to[i];
			if(col[q]>=0) {ret&=(col[q]==(col[p]+w[i])%3);continue;}
			
			tmp++;
			col[q]=(col[p]+w[i])%3;
			ret&=dfs(q);
		}
		return ret;
	}
	void solve()
	{
		initialize();
		for(int i=1;i<=n;i++)col[i]=-1;

		ans=0;
		int ct=0;
		for(int i=1;i<=n;i++)
			if(col[i]<0)
			{
				ct++;
				
				tmp=cnt[0]=cnt[1]=cnt[2]=col[i]=0;
				if(dfs(i))
				{
					if(cnt[0] && cnt[1] && cnt[2])
						ans+=(ll)cnt[0]*cnt[1]+(ll)cnt[1]*cnt[2]+(ll)cnt[0]*cnt[2];
					else ans+=tmp;
				}
				else ans+=(ll)(cnt[0]+cnt[1]+cnt[2])*(cnt[0]+cnt[1]+cnt[2]);
			}

		printf("%lld\n",ans);
	}
}
int main()
{
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	fucker::solve();
	return 0;
}

Submission Info

Submission Time
Task F - Blackout
User Demerzel_IV
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1442 Byte
Status WA
Exec Time 19 ms
Memory 8064 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1700
Status
AC × 3
AC × 52
WA × 1
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 2 ms 640 KB
1_02.txt AC 12 ms 3328 KB
1_03.txt AC 14 ms 8064 KB
1_04.txt AC 15 ms 8064 KB
1_05.txt AC 14 ms 8064 KB
1_06.txt AC 14 ms 8064 KB
1_07.txt AC 14 ms 8064 KB
1_08.txt AC 14 ms 8064 KB
1_09.txt AC 14 ms 8064 KB
1_10.txt AC 14 ms 8064 KB
1_11.txt AC 14 ms 8064 KB
1_12.txt AC 14 ms 8064 KB
1_13.txt WA 14 ms 8064 KB
1_14.txt AC 10 ms 3328 KB
1_15.txt AC 9 ms 3328 KB
1_16.txt AC 9 ms 3328 KB
1_17.txt AC 9 ms 2560 KB
1_18.txt AC 19 ms 4608 KB
1_19.txt AC 19 ms 4608 KB
1_20.txt AC 18 ms 4480 KB
1_21.txt AC 19 ms 4608 KB
1_22.txt AC 18 ms 4608 KB
1_23.txt AC 19 ms 4608 KB
1_24.txt AC 18 ms 4480 KB
1_25.txt AC 19 ms 4608 KB
1_26.txt AC 19 ms 4608 KB
1_27.txt AC 19 ms 4480 KB
1_28.txt AC 19 ms 4480 KB
1_29.txt AC 19 ms 4608 KB
1_30.txt AC 19 ms 4480 KB
1_31.txt AC 18 ms 4608 KB
1_32.txt AC 18 ms 4608 KB
1_33.txt AC 19 ms 4608 KB
1_34.txt AC 18 ms 4608 KB
1_35.txt AC 17 ms 4224 KB
1_36.txt AC 18 ms 4480 KB
1_37.txt AC 18 ms 4608 KB
1_38.txt AC 16 ms 3968 KB
1_39.txt AC 16 ms 3712 KB
1_40.txt AC 19 ms 4608 KB
1_41.txt AC 19 ms 4608 KB
1_42.txt AC 16 ms 4224 KB
1_43.txt AC 17 ms 4224 KB
1_44.txt AC 18 ms 4608 KB
1_45.txt AC 16 ms 3584 KB
1_46.txt AC 18 ms 4608 KB
1_47.txt AC 18 ms 4608 KB
1_48.txt AC 17 ms 4096 KB
1_49.txt AC 18 ms 4480 KB