oj.uz

Submission #1057988

# Submission time Handle Problem Language Result Execution time Memory
1057988 2024-08-14T07:51:29 Z fuad27 Digital Circuit (IOI22_circuit) C++17
2 / 100
 3000 ms 6232 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022; // ????? 
const int N = 1e5+10;
vector<int> child[N];
long long total[N];
long long contrib[N];

void dfs(int at) {
	total[at] = max(1, (int)child[at].size());
	for(int to:child[at]) {
		dfs(to);
		total[at] = (total[at] * total[to])%mod;
	}
}
void dfs2(int at) {
	long long sumtot = 0;
	for(int to:child[at]) {
		sumtot+=total[to];
		sumtot%=mod;
	}
	int c = child[at].size();
	long long pref[c];
	pref[0] = 1;
	for(int i = 1;i<c;i++) {
		pref[i] = (pref[i-1] * total[child[at][i-1]])%mod;
	}
	long long suff = 1;
	for(int i = c-1;i>=0;i--) {
		contrib[child[at][i]] = (((suff*pref[i])%mod)*contrib[at])%mod;
		dfs2(child[at][i]);
		suff = (suff*total[child[at][i]])%mod;
	}
}
vector<int> A;
int nn;
void init(int n, int m, std::vector<int> p, std::vector<int> a) {
	nn=n;
	A = a;
	for(int i = 1;i<m+n;i++) {
		child[p[i]].push_back(i);
	}
	for(int i= 0;i<m+n;i++)contrib[i] = 1;
	dfs(0);
	dfs2(0);
}

int count_ways(int L, int R) {
	L-=nn, R-=nn;
	for(int i = L;i<=R;i++)A[i]^=1;
	long long sum = 0;
	for(int i = 0;i<(int)A.size();i++) {
		sum=(sum+(1-A[i])*contrib[nn+i])%mod;
	}
	int ans = (total[0]-sum)%mod;
	return ans;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3924 KB Output is correct
2 Incorrect 1 ms 4184 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '-214716416'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4184 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4184 KB Output is correct
7 Correct 1 ms 4184 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 1 ms 3924 KB Output is correct
10 Incorrect 1 ms 4184 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '-214716416'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 6232 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 3047 ms 6232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3924 KB Output is correct
2 Incorrect 1 ms 4184 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '-214716416'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4184 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4184 KB Output is correct
7 Correct 1 ms 4184 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 1 ms 3924 KB Output is correct
10 Incorrect 1 ms 4184 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '-214716416'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4184 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4184 KB Output is correct
7 Correct 1 ms 4184 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 1 ms 3924 KB Output is correct
10 Incorrect 1 ms 4184 KB 2nd lines differ - on the 1st token, expected: '785285606', found: '-214716416'
11 Halted 0 ms 0 KB -