oj.uz

Submission #930190

# Submission time Handle Problem Language Result Execution time Memory
930190 2024-02-18T22:04:40 Z Edu175 Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 22952 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define dfore(i,a,b) for(ll i=b-1,ioi=a;i>=ioi;i--)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto djfhg:v)cout<<djfhg<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=2e5+5,MOD=1000002022;
int add(int a, int b){a+=b;if(a>=MOD)a-=MOD;return a;}
int sub(int a, int b){a-=b;if(a<0)a+=MOD;return a;}
int mul(ll a, ll b){return a*b%MOD;}

ll n,m;
vector<ll>g[MAXN];
ll a[MAXN],tot[MAXN],dp[MAXN];
vector<ll> pre[MAXN], suf[MAXN];
void init(int N, int M, std::vector<int> P, std::vector<int> A){
	n=N,m=M;
	fore(i,0,SZ(P)){
		if(P[i]!=-1)g[P[i]].pb(i);
	}
	fore(i,0,m)a[i+n]=A[i];
	fore(i,0,m)tot[n+i]=1;
	dfore(x,0,n){
		ll k=SZ(g[x]);
		tot[x]=k;
		for(auto y:g[x])tot[x]=mul(tot[x],tot[y]);
		pre[x].resize(k+1,1),suf[x].resize(k+1,1);
		fore(i,1,k+1)pre[x][i]=mul(pre[x][i-1],tot[g[x][i-1]]);
		dfore(i,0,k)suf[x][i]=mul(suf[x][i+1],tot[g[x][i]]);
	}
}

int count_ways(int L, int R){
	fore(i,L,R+1)a[i]^=1;
	//fore(i,n,n+m)cout<<a[i];;cout<<"\n";
	dfore(x,0,n+m){
		dp[x]=0;
		if(x>=n)dp[x]=a[x];
		else {
			fore(i,0,SZ(g[x])){
				auto y=g[x][i];
				dp[x]=add(dp[x],mul(dp[y],mul(pre[x][i],suf[x][i+1])));
			}
		}
		//cout<<x<<": "<<dp[x]<<"\n";
	}
	return dp[0];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19288 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19028 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19288 KB Output is correct
7 Correct 4 ms 19280 KB Output is correct
8 Correct 4 ms 19200 KB Output is correct
9 Correct 4 ms 19240 KB Output is correct
10 Correct 4 ms 19288 KB Output is correct
11 Correct 4 ms 19288 KB Output is correct
12 Correct 4 ms 19540 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19288 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19032 KB Output is correct
10 Correct 4 ms 19028 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 19032 KB Output is correct
13 Correct 4 ms 19032 KB Output is correct
14 Correct 4 ms 19288 KB Output is correct
15 Correct 4 ms 19280 KB Output is correct
16 Correct 4 ms 19200 KB Output is correct
17 Correct 4 ms 19240 KB Output is correct
18 Correct 4 ms 19288 KB Output is correct
19 Correct 4 ms 19288 KB Output is correct
20 Correct 4 ms 19540 KB Output is correct
21 Correct 4 ms 19288 KB Output is correct
22 Correct 4 ms 19288 KB Output is correct
23 Correct 4 ms 19288 KB Output is correct
24 Correct 4 ms 19228 KB Output is correct
25 Correct 4 ms 19288 KB Output is correct
26 Correct 4 ms 19288 KB Output is correct
27 Correct 4 ms 19288 KB Output is correct
28 Correct 4 ms 19540 KB Output is correct
29 Correct 4 ms 19032 KB Output is correct
30 Correct 5 ms 19032 KB Output is correct
31 Correct 4 ms 19288 KB Output is correct
32 Correct 4 ms 19288 KB Output is correct
33 Correct 4 ms 19288 KB Output is correct
34 Correct 4 ms 19032 KB Output is correct
35 Correct 4 ms 19032 KB Output is correct
36 Correct 4 ms 19288 KB Output is correct
37 Correct 4 ms 19204 KB Output is correct
38 Correct 4 ms 19356 KB Output is correct
39 Correct 4 ms 19288 KB Output is correct
40 Correct 4 ms 19288 KB Output is correct
41 Correct 4 ms 19288 KB Output is correct
42 Correct 4 ms 19280 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3095 ms 22952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3095 ms 22952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 4 ms 19028 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19288 KB Output is correct
7 Correct 4 ms 19280 KB Output is correct
8 Correct 4 ms 19200 KB Output is correct
9 Correct 4 ms 19240 KB Output is correct
10 Correct 4 ms 19288 KB Output is correct
11 Correct 4 ms 19288 KB Output is correct
12 Correct 4 ms 19540 KB Output is correct
13 Execution timed out 3095 ms 22952 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19288 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19032 KB Output is correct
10 Correct 4 ms 19028 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 19032 KB Output is correct
13 Correct 4 ms 19032 KB Output is correct
14 Correct 4 ms 19288 KB Output is correct
15 Correct 4 ms 19280 KB Output is correct
16 Correct 4 ms 19200 KB Output is correct
17 Correct 4 ms 19240 KB Output is correct
18 Correct 4 ms 19288 KB Output is correct
19 Correct 4 ms 19288 KB Output is correct
20 Correct 4 ms 19540 KB Output is correct
21 Correct 4 ms 19288 KB Output is correct
22 Correct 4 ms 19288 KB Output is correct
23 Correct 4 ms 19288 KB Output is correct
24 Correct 4 ms 19228 KB Output is correct
25 Correct 4 ms 19288 KB Output is correct
26 Correct 4 ms 19288 KB Output is correct
27 Correct 4 ms 19288 KB Output is correct
28 Correct 4 ms 19540 KB Output is correct
29 Correct 4 ms 19032 KB Output is correct
30 Correct 5 ms 19032 KB Output is correct
31 Correct 4 ms 19288 KB Output is correct
32 Correct 4 ms 19288 KB Output is correct
33 Correct 4 ms 19288 KB Output is correct
34 Correct 4 ms 19032 KB Output is correct
35 Correct 4 ms 19032 KB Output is correct
36 Correct 4 ms 19288 KB Output is correct
37 Correct 4 ms 19204 KB Output is correct
38 Correct 4 ms 19356 KB Output is correct
39 Correct 4 ms 19288 KB Output is correct
40 Correct 4 ms 19288 KB Output is correct
41 Correct 4 ms 19288 KB Output is correct
42 Correct 4 ms 19280 KB Output is correct
43 Correct 2673 ms 19544 KB Output is correct
44 Execution timed out 3070 ms 19544 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19288 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19032 KB Output is correct
10 Correct 4 ms 19028 KB Output is correct
11 Correct 4 ms 19032 KB Output is correct
12 Correct 4 ms 19032 KB Output is correct
13 Correct 4 ms 19032 KB Output is correct
14 Correct 4 ms 19288 KB Output is correct
15 Correct 4 ms 19280 KB Output is correct
16 Correct 4 ms 19200 KB Output is correct
17 Correct 4 ms 19240 KB Output is correct
18 Correct 4 ms 19288 KB Output is correct
19 Correct 4 ms 19288 KB Output is correct
20 Correct 4 ms 19540 KB Output is correct
21 Correct 4 ms 19288 KB Output is correct
22 Correct 4 ms 19288 KB Output is correct
23 Correct 4 ms 19288 KB Output is correct
24 Correct 4 ms 19228 KB Output is correct
25 Correct 4 ms 19288 KB Output is correct
26 Correct 4 ms 19288 KB Output is correct
27 Correct 4 ms 19288 KB Output is correct
28 Correct 4 ms 19540 KB Output is correct
29 Correct 4 ms 19032 KB Output is correct
30 Correct 5 ms 19032 KB Output is correct
31 Correct 4 ms 19288 KB Output is correct
32 Correct 4 ms 19288 KB Output is correct
33 Correct 4 ms 19288 KB Output is correct
34 Correct 4 ms 19032 KB Output is correct
35 Correct 4 ms 19032 KB Output is correct
36 Correct 4 ms 19288 KB Output is correct
37 Correct 4 ms 19204 KB Output is correct
38 Correct 4 ms 19356 KB Output is correct
39 Correct 4 ms 19288 KB Output is correct
40 Correct 4 ms 19288 KB Output is correct
41 Correct 4 ms 19288 KB Output is correct
42 Correct 4 ms 19280 KB Output is correct
43 Execution timed out 3095 ms 22952 KB Time limit exceeded
44 Halted 0 ms 0 KB -