oj.uz

Submission #737505

# Submission time Handle Problem Language Result Execution time Memory
737505 2023-05-07T09:04:33 Z minhcool Digital Circuit (IOI22_circuit) C++17
18 / 100
 51 ms 33928 KB 
#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 5e3 + 5;
 
const int oo = 1e18 + 7, mod = 1000002022;
 
int n, m;
vector<int> Adj[N];
 
int arr[N];
 
long long coor[N][N];
long long pref[N], suff[N];
 
void dfs(int u){
	if(!Adj[u].size()) return;
	for(auto v : Adj[u]) dfs(v);
	pref[0] = coor[Adj[u][0]][m];
	for(int i = 1; i < Adj[u].size(); i++) pref[i] = (pref[i - 1] * coor[Adj[u][i]][m]) % mod;
	suff[Adj[u].size()] = 1;
	for(int i = Adj[u].size() - 1; i >= 0; i--) suff[i] = (suff[i + 1] * coor[Adj[u][i]][m]) % mod;
	//for(int i = 0; i < Adj[u].size(); i++) cout << pref[i] << " " << suff[i] << "\n";
	coor[u][m] = (pref[Adj[u].size() - 1] * Adj[u].size()) % mod;
	for(int i = 0; i < Adj[u].size(); i++){
		for(int j = 0; j < m; j++){
			long long temp1 = (!i ? 1 : pref[i - 1]);
			temp1 = (temp1 * suff[i + 1]) % mod;
			temp1 = (temp1 * coor[Adj[u][i]][j]) % mod;
			coor[u][j] = (coor[u][j] + temp1) % mod;
		}
	}
	for(int i = 0; i <= m; i++) coor[u][i] = ((coor[u][i] % mod) + mod) % mod;
	//for(int i = 0; i <= m; i++) cout << u << " " << i << " " << coor[u][i] << "\n";
}
 
void init(int N, int M, vector<int> P, vector<int> A){
	n = N, m = M;
	for(int i = 1; i < n + m; i++) Adj[P[i]].pb(i);
	for(int i = 0; i < m; i++) arr[i] = A[i];
	for(int i = n; i < n + m; i++) coor[i][i - n] = coor[i][m] = 1;
	dfs(0);
	//for(int i = 0; i < m; i++) cout << coor[0][i] << " ";
	//cout << "\n";
}
 
int count_ways(int L, int R){
	L -= n, R -= n;
	for(int i = L; i <= R; i++) arr[i] ^= 1;
	long long ans = 0;
	for(int i = 0; i < m; i++) ans = (ans + (long long)arr[i] * coor[0][i]) % mod;
	ans = ((ans % mod) + mod) % mod;
	int ans2 = ans;
	return ans2;
}

Compilation message

circuit.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1000002022;
      |                ~~~~~^~~
circuit.cpp: In function 'void dfs(int)':
circuit.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 1; i < Adj[u].size(); i++) pref[i] = (pref[i - 1] * coor[Adj[u][i]][m]) % mod;
      |                 ~~^~~~~~~~~~~~~~~
circuit.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < Adj[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 10 ms 7312 KB Output is correct
4 Correct 8 ms 7504 KB Output is correct
5 Correct 9 ms 7508 KB Output is correct
6 Correct 8 ms 7504 KB Output is correct
7 Correct 8 ms 7540 KB Output is correct
8 Correct 9 ms 7504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 3280 KB Output is correct
3 Correct 6 ms 7652 KB Output is correct
4 Correct 7 ms 7632 KB Output is correct
5 Correct 7 ms 7632 KB Output is correct
6 Correct 12 ms 12368 KB Output is correct
7 Correct 21 ms 19408 KB Output is correct
8 Correct 20 ms 19408 KB Output is correct
9 Correct 20 ms 19356 KB Output is correct
10 Correct 21 ms 19480 KB Output is correct
11 Correct 20 ms 19400 KB Output is correct
12 Correct 15 ms 15376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 10 ms 7312 KB Output is correct
4 Correct 8 ms 7504 KB Output is correct
5 Correct 9 ms 7508 KB Output is correct
6 Correct 8 ms 7504 KB Output is correct
7 Correct 8 ms 7540 KB Output is correct
8 Correct 9 ms 7504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 3280 KB Output is correct
11 Correct 6 ms 7652 KB Output is correct
12 Correct 7 ms 7632 KB Output is correct
13 Correct 7 ms 7632 KB Output is correct
14 Correct 12 ms 12368 KB Output is correct
15 Correct 21 ms 19408 KB Output is correct
16 Correct 20 ms 19408 KB Output is correct
17 Correct 20 ms 19356 KB Output is correct
18 Correct 21 ms 19480 KB Output is correct
19 Correct 20 ms 19400 KB Output is correct
20 Correct 15 ms 15376 KB Output is correct
21 Correct 15 ms 15228 KB Output is correct
22 Correct 9 ms 9664 KB Output is correct
23 Correct 9 ms 9312 KB Output is correct
24 Correct 22 ms 19340 KB Output is correct
25 Correct 21 ms 19340 KB Output is correct
26 Correct 23 ms 19436 KB Output is correct
27 Correct 21 ms 19360 KB Output is correct
28 Correct 20 ms 19408 KB Output is correct
29 Correct 9 ms 7504 KB Output is correct
30 Correct 8 ms 7468 KB Output is correct
31 Correct 3 ms 4560 KB Output is correct
32 Correct 28 ms 19324 KB Output is correct
33 Correct 15 ms 13392 KB Output is correct
34 Correct 11 ms 10448 KB Output is correct
35 Correct 7 ms 6608 KB Output is correct
36 Correct 21 ms 19524 KB Output is correct
37 Correct 20 ms 19456 KB Output is correct
38 Correct 22 ms 19496 KB Output is correct
39 Correct 8 ms 8028 KB Output is correct
40 Correct 11 ms 11344 KB Output is correct
41 Correct 11 ms 10440 KB Output is correct
42 Correct 8 ms 7504 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 2488 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 12 ms 2488 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 1 ms 336 KB Output is correct
2 Correct 3 ms 3280 KB Output is correct
3 Correct 6 ms 7652 KB Output is correct
4 Correct 7 ms 7632 KB Output is correct
5 Correct 7 ms 7632 KB Output is correct
6 Correct 12 ms 12368 KB Output is correct
7 Correct 21 ms 19408 KB Output is correct
8 Correct 20 ms 19408 KB Output is correct
9 Correct 20 ms 19356 KB Output is correct
10 Correct 21 ms 19480 KB Output is correct
11 Correct 20 ms 19400 KB Output is correct
12 Correct 15 ms 15376 KB Output is correct
13 Runtime error 12 ms 2488 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 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 10 ms 7312 KB Output is correct
4 Correct 8 ms 7504 KB Output is correct
5 Correct 9 ms 7508 KB Output is correct
6 Correct 8 ms 7504 KB Output is correct
7 Correct 8 ms 7540 KB Output is correct
8 Correct 9 ms 7504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 3280 KB Output is correct
11 Correct 6 ms 7652 KB Output is correct
12 Correct 7 ms 7632 KB Output is correct
13 Correct 7 ms 7632 KB Output is correct
14 Correct 12 ms 12368 KB Output is correct
15 Correct 21 ms 19408 KB Output is correct
16 Correct 20 ms 19408 KB Output is correct
17 Correct 20 ms 19356 KB Output is correct
18 Correct 21 ms 19480 KB Output is correct
19 Correct 20 ms 19400 KB Output is correct
20 Correct 15 ms 15376 KB Output is correct
21 Correct 15 ms 15228 KB Output is correct
22 Correct 9 ms 9664 KB Output is correct
23 Correct 9 ms 9312 KB Output is correct
24 Correct 22 ms 19340 KB Output is correct
25 Correct 21 ms 19340 KB Output is correct
26 Correct 23 ms 19436 KB Output is correct
27 Correct 21 ms 19360 KB Output is correct
28 Correct 20 ms 19408 KB Output is correct
29 Correct 9 ms 7504 KB Output is correct
30 Correct 8 ms 7468 KB Output is correct
31 Correct 3 ms 4560 KB Output is correct
32 Correct 28 ms 19324 KB Output is correct
33 Correct 15 ms 13392 KB Output is correct
34 Correct 11 ms 10448 KB Output is correct
35 Correct 7 ms 6608 KB Output is correct
36 Correct 21 ms 19524 KB Output is correct
37 Correct 20 ms 19456 KB Output is correct
38 Correct 22 ms 19496 KB Output is correct
39 Correct 8 ms 8028 KB Output is correct
40 Correct 11 ms 11344 KB Output is correct
41 Correct 11 ms 10440 KB Output is correct
42 Correct 8 ms 7504 KB Output is correct
43 Runtime error 51 ms 33928 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 10 ms 7312 KB Output is correct
4 Correct 8 ms 7504 KB Output is correct
5 Correct 9 ms 7508 KB Output is correct
6 Correct 8 ms 7504 KB Output is correct
7 Correct 8 ms 7540 KB Output is correct
8 Correct 9 ms 7504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 3280 KB Output is correct
11 Correct 6 ms 7652 KB Output is correct
12 Correct 7 ms 7632 KB Output is correct
13 Correct 7 ms 7632 KB Output is correct
14 Correct 12 ms 12368 KB Output is correct
15 Correct 21 ms 19408 KB Output is correct
16 Correct 20 ms 19408 KB Output is correct
17 Correct 20 ms 19356 KB Output is correct
18 Correct 21 ms 19480 KB Output is correct
19 Correct 20 ms 19400 KB Output is correct
20 Correct 15 ms 15376 KB Output is correct
21 Correct 15 ms 15228 KB Output is correct
22 Correct 9 ms 9664 KB Output is correct
23 Correct 9 ms 9312 KB Output is correct
24 Correct 22 ms 19340 KB Output is correct
25 Correct 21 ms 19340 KB Output is correct
26 Correct 23 ms 19436 KB Output is correct
27 Correct 21 ms 19360 KB Output is correct
28 Correct 20 ms 19408 KB Output is correct
29 Correct 9 ms 7504 KB Output is correct
30 Correct 8 ms 7468 KB Output is correct
31 Correct 3 ms 4560 KB Output is correct
32 Correct 28 ms 19324 KB Output is correct
33 Correct 15 ms 13392 KB Output is correct
34 Correct 11 ms 10448 KB Output is correct
35 Correct 7 ms 6608 KB Output is correct
36 Correct 21 ms 19524 KB Output is correct
37 Correct 20 ms 19456 KB Output is correct
38 Correct 22 ms 19496 KB Output is correct
39 Correct 8 ms 8028 KB Output is correct
40 Correct 11 ms 11344 KB Output is correct
41 Correct 11 ms 10440 KB Output is correct
42 Correct 8 ms 7504 KB Output is correct
43 Runtime error 12 ms 2488 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -