Submission #19453926


Source Code Expand

Copy
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define popb pop_back
#define all(A) A.begin(),A.end()
#define rall(A) A.rbegin(),A.rend()
#define dic unordered_map
#define bpc __builtin_popcountll//numero de bits para long long
#define bclz __builtin_clzll//leading zeros para ll
#define max_bit(A) 31-__builtin_clz(A)
using namespace std;
const int maxn=1e5;
const ll mod=998244353;

int mid[maxn][5];
ll dp[maxn][2];

ll fpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	map<pair<int,int>,int> mp;
	vector<int> cnt(n,0);
	for(int i=3;i<n;i++) cnt[i]=i-2;
	for(int i=0;i<n;i++) for(int j=0;j<5;j++) mid[i][j]=-1;
	for(int i=0;i<m;i++){
		int a,b,c,d;
		cin>>a>>b>>c;
		a--,b--;
		d=max(a,b);
		if(max(a,b)-min(a,b)>2){
			mp[{a,b}]=c;
			if(mp.count({b,a})){
				if((mp[{a,b}]+mp[{b,a}])&1){
					cout<<"0\n";
					return 0;
				}
			} else cnt[d]--;
		}else{
			mid[d][a-b+2]=c;
		}
	}
	if(mid[0][2]==-1) dp[0][1]=dp[0][0]=1;
	else dp[0][mid[0][2]]=1,dp[0][mid[0][2]^1]=0;
	int libre=0,libre2;
	libre+=mid[1][1]==-1;
	libre+=mid[1][3]==-1;
	dp[1][0]=dp[1][1]=0;
	for(int i=0;i<2;i++){
		if(mid[1][2]==-1){
			for(int j=0;j<2;j++){
				if(libre){
					dp[1][j]+=dp[0][i]*fpow(2,libre-1);
				}else{
					if((i+j+mid[1][1]+mid[1][3])&1) continue;
					else dp[1][j]+=dp[0][i];
				}
			}
		}else{
			if(libre) dp[1][mid[1][2]]+=dp[0][i]*fpow(2,libre-1);
			else{
				if((i+mid[1][2]+mid[1][1]+mid[1][3])&1) continue;
				else dp[1][mid[1][2]]+=dp[0][i];
			}
		}
	}
	for(int k=2;k<n;k++){
		libre=0,libre2=0;
		libre+=mid[k][1]==-1;
		libre+=mid[k][3]==-1;
		libre2+=mid[k][0]==-1;
		libre2+=mid[k][4]==-1;
		dp[k][0]=dp[k][1]=0;
		for(int i=0;i<2;i++){
			if(mid[k][2]==-1){
				for(int j=0;j<2;j++){
					ll res;
					if(libre) res=(dp[k-1][i]*fpow(2,libre-1))%mod;
					else{
						if((i+j+mid[k][1]+mid[k][3])&1) continue;
						else res=dp[k-1][i];
					}
					if(libre2) res=(res*fpow(2,libre2-1))%mod;
					else if((mid[k][0]+mid[k][4])&1!=i) continue; 
					dp[k][i]=(dp[k][i]+res)%mod;
				}
			}else{
				ll res;
				if(libre) res=(dp[k-1][i]*fpow(2,libre-1))%mod;
				else{
					if((i+mid[k][2]+mid[k][1]+mid[k][3])&1) continue;
					else res=dp[k-1][i];
				}
				if(libre2) res=(res*fpow(2,libre2-1))%mod;
				else if((mid[k][0]+mid[k][4])&1!=i) continue;
				dp[k][mid[k][2]]=(dp[k][mid[k][2]]+res)%mod;
			}
		}
		ll e=fpow(2,cnt[k]);
		dp[k][0]=(dp[k][0]*e)%mod;
		dp[k][1]=(dp[k][1]*e)%mod;
	}
	//for(int i=0;i<n;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<"\n";
	cout<<(dp[n-1][0]+dp[n-1][1])%mod<<"\n";
	// your code goes here
	return 0;
}

Submission Info

Submission Time
Task F - Square
User MOONMEANDER_FP
Language C++ (GCC 9.2.1)
Score 0
Code Size 2823 Byte
Status WA
Exec Time 60 ms
Memory 10192 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:37: warning: suggest parentheses around comparison in operand of ‘&’ [-Wparentheses]
   94 |      else if((mid[k][0]+mid[k][4])&1!=i) continue;
      |                                    ~^~~
./Main.cpp:105:36: warning: suggest parentheses around comparison in operand of ‘&’ [-Wparentheses]
  105 |     else if((mid[k][0]+mid[k][4])&1!=i) continue;
      |                                   ~^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 5
AC × 63
WA × 30
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 80.txt, 81.txt, 82.txt, 83.txt, 84.txt, 85.txt, 86.txt, 87.txt, 88.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
Case Name Status Exec Time Memory
01.txt AC 19 ms 3992 KB
02.txt WA 16 ms 3860 KB
03.txt AC 25 ms 3924 KB
04.txt AC 19 ms 4004 KB
05.txt WA 26 ms 4988 KB
06.txt AC 16 ms 3932 KB
07.txt AC 18 ms 3868 KB
08.txt WA 28 ms 5100 KB
09.txt AC 22 ms 3872 KB
10.txt AC 19 ms 4008 KB
11.txt AC 20 ms 3888 KB
12.txt AC 17 ms 3868 KB
13.txt AC 16 ms 3920 KB
14.txt WA 18 ms 3872 KB
15.txt AC 18 ms 3864 KB
16.txt WA 20 ms 3924 KB
17.txt AC 16 ms 3936 KB
18.txt AC 19 ms 3900 KB
19.txt WA 33 ms 7008 KB
20.txt WA 35 ms 7068 KB
21.txt WA 34 ms 7040 KB
22.txt WA 37 ms 7112 KB
23.txt WA 39 ms 7136 KB
24.txt WA 29 ms 7072 KB
25.txt AC 16 ms 4348 KB
26.txt AC 21 ms 4828 KB
27.txt AC 10 ms 4132 KB
28.txt AC 9 ms 3828 KB
29.txt AC 60 ms 10188 KB
30.txt AC 51 ms 10192 KB
31.txt WA 21 ms 4256 KB
32.txt WA 18 ms 4204 KB
33.txt AC 18 ms 4152 KB
34.txt WA 21 ms 4252 KB
35.txt AC 17 ms 4260 KB
36.txt AC 17 ms 4216 KB
37.txt WA 35 ms 7076 KB
38.txt WA 30 ms 6976 KB
39.txt AC 21 ms 4456 KB
40.txt AC 21 ms 4472 KB
41.txt AC 18 ms 4592 KB
42.txt AC 21 ms 4408 KB
43.txt WA 19 ms 4536 KB
44.txt AC 27 ms 4412 KB
45.txt WA 20 ms 4576 KB
46.txt WA 18 ms 4516 KB
47.txt WA 25 ms 4516 KB
48.txt WA 25 ms 4576 KB
49.txt AC 24 ms 4584 KB
50.txt AC 20 ms 4572 KB
51.txt WA 35 ms 7112 KB
52.txt WA 34 ms 7052 KB
53.txt WA 33 ms 7116 KB
54.txt WA 35 ms 7076 KB
55.txt AC 23 ms 5348 KB
56.txt AC 28 ms 5348 KB
57.txt AC 28 ms 7072 KB
58.txt AC 34 ms 6988 KB
59.txt AC 27 ms 7104 KB
60.txt AC 35 ms 6976 KB
61.txt WA 33 ms 6988 KB
62.txt AC 29 ms 7080 KB
63.txt AC 31 ms 6948 KB
64.txt AC 33 ms 7120 KB
65.txt AC 37 ms 7136 KB
66.txt AC 30 ms 7076 KB
67.txt AC 31 ms 7112 KB
68.txt AC 32 ms 7068 KB
69.txt AC 31 ms 7040 KB
70.txt AC 29 ms 7040 KB
71.txt WA 32 ms 7140 KB
72.txt WA 35 ms 6944 KB
73.txt AC 34 ms 6988 KB
74.txt AC 35 ms 6980 KB
75.txt AC 32 ms 7116 KB
76.txt AC 33 ms 7068 KB
77.txt AC 2 ms 3484 KB
78.txt AC 2 ms 3596 KB
79.txt AC 2 ms 3540 KB
80.txt AC 1 ms 3524 KB
81.txt AC 2 ms 3592 KB
82.txt AC 3 ms 3548 KB
83.txt AC 3 ms 3604 KB
84.txt AC 2 ms 3588 KB
85.txt AC 22 ms 6996 KB
86.txt AC 20 ms 7108 KB
87.txt WA 2 ms 3588 KB
88.txt WA 3 ms 3524 KB
s1.txt AC 2 ms 3552 KB
s2.txt AC 2 ms 3520 KB
s3.txt AC 2 ms 3484 KB
s4.txt AC 3 ms 3588 KB
s5.txt AC 22 ms 7036 KB