Submission #666991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
666991	2022-11-30T06:48:49 Z	mychecksedad	Digital Circuit (IOI22_circuit)	C++17	9 / 100	10 ms	2756 KB

circuit

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 2e3 + 10, MOD = 1000002022;

int n, m;
ll ans[N][2];
vector<ll> dp[N];
vector<int> source, g[N];
void calculate(int v, int u){
	int s = g[v].size(); 
	v ? s-- : 1;
	vector<ll> temp(s + 2, 0);

	for(int i = 0; i <= s; ++i){
		if(i > 0)
			temp[i] += dp[v][i - 1] * ans[u][1];
		temp[i] += dp[v][i] * ans[u][0];
	}

	dp[v] = temp;
}

void dfs(int v, int p){
	if(v >= n){
		ans[v][source[v - n]] = 1;
		ans[v][source[v - n] ^ 1] = 0;
		return;
	}
	int s = g[v].size();
	v ? s-- : 1;
	dp[v].clear();
	dp[v].resize(s + 2, 0);
	dp[v][0] = 1;
	for(int u: g[v]){
		if(u != p){
			dfs(u, v);
			calculate(v, u);
		}
	}
	ans[v][0] = ans[v][1] = 0;
	for(ll i = 0; i <= s; ++i){
		(ans[v][0] += dp[v][i] * (s - i)) %= MOD;
		(ans[v][1] += dp[v][i] * i) %= MOD;
	}
}

void init(int N, int M, vector<int> P, vector<int> A){
	source = A;
	n = N;
	m = M;
	for(int i = 1; i < n + m; ++i){
		g[i].pb(P[i]);
		g[P[i]].pb(i);
	}
}


int count_ways(int L, int R){
	L -= n, R -= n;
	for(int i = L; i <= R; ++i) source[i] ^= 1;
	dfs(0, 0);
	return ans[0][1];
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	7 ms	464 KB	Output is correct
4	Correct	9 ms	464 KB	Output is correct
5	Correct	9 ms	472 KB	Output is correct
6	Correct	8 ms	464 KB	Output is correct
7	Correct	8 ms	464 KB	Output is correct
8	Correct	9 ms	464 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	2 ms	464 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	1 ms	464 KB	Output is correct
7	Correct	3 ms	464 KB	Output is correct
8	Correct	2 ms	464 KB	Output is correct
9	Correct	1 ms	528 KB	Output is correct
10	Correct	1 ms	592 KB	Output is correct
11	Correct	2 ms	592 KB	Output is correct
12	Correct	1 ms	464 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	7 ms	464 KB	Output is correct
4	Correct	9 ms	464 KB	Output is correct
5	Correct	9 ms	472 KB	Output is correct
6	Correct	8 ms	464 KB	Output is correct
7	Correct	8 ms	464 KB	Output is correct
8	Correct	9 ms	464 KB	Output is correct
9	Correct	0 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	2 ms	464 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	1 ms	464 KB	Output is correct
15	Correct	3 ms	464 KB	Output is correct
16	Correct	2 ms	464 KB	Output is correct
17	Correct	1 ms	528 KB	Output is correct
18	Correct	1 ms	592 KB	Output is correct
19	Correct	2 ms	592 KB	Output is correct
20	Correct	1 ms	464 KB	Output is correct
21	Incorrect	1 ms	464 KB	1st lines differ - on the 1st token, expected: '759476520', found: '674134980'
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	2756 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	2756 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	2 ms	464 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	1 ms	464 KB	Output is correct
7	Correct	3 ms	464 KB	Output is correct
8	Correct	2 ms	464 KB	Output is correct
9	Correct	1 ms	528 KB	Output is correct
10	Correct	1 ms	592 KB	Output is correct
11	Correct	2 ms	592 KB	Output is correct
12	Correct	1 ms	464 KB	Output is correct
13	Runtime error	10 ms	2756 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	7 ms	464 KB	Output is correct
4	Correct	9 ms	464 KB	Output is correct
5	Correct	9 ms	472 KB	Output is correct
6	Correct	8 ms	464 KB	Output is correct
7	Correct	8 ms	464 KB	Output is correct
8	Correct	9 ms	464 KB	Output is correct
9	Correct	0 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	2 ms	464 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	1 ms	464 KB	Output is correct
15	Correct	3 ms	464 KB	Output is correct
16	Correct	2 ms	464 KB	Output is correct
17	Correct	1 ms	528 KB	Output is correct
18	Correct	1 ms	592 KB	Output is correct
19	Correct	2 ms	592 KB	Output is correct
20	Correct	1 ms	464 KB	Output is correct
21	Incorrect	1 ms	464 KB	1st lines differ - on the 1st token, expected: '759476520', found: '674134980'
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	336 KB	Output is correct
2	Correct	0 ms	336 KB	Output is correct
3	Correct	7 ms	464 KB	Output is correct
4	Correct	9 ms	464 KB	Output is correct
5	Correct	9 ms	472 KB	Output is correct
6	Correct	8 ms	464 KB	Output is correct
7	Correct	8 ms	464 KB	Output is correct
8	Correct	9 ms	464 KB	Output is correct
9	Correct	0 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	2 ms	464 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	1 ms	464 KB	Output is correct
15	Correct	3 ms	464 KB	Output is correct
16	Correct	2 ms	464 KB	Output is correct
17	Correct	1 ms	528 KB	Output is correct
18	Correct	1 ms	592 KB	Output is correct
19	Correct	2 ms	592 KB	Output is correct
20	Correct	1 ms	464 KB	Output is correct
21	Incorrect	1 ms	464 KB	1st lines differ - on the 1st token, expected: '759476520', found: '674134980'
22	Halted	0 ms	0 KB	-

Submission #666991

Compilation message