Submission #637190

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
637190	2022-08-31T21:50:31 Z	blue	Digital Circuit (IOI22_circuit)	C++17	13 / 100	3000 ms	11980 KB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

const ll mod = 1'000'002'022;

ll ad(ll a, ll b)
{
	return (a+b)%mod;
}

ll mul(ll a, ll b)
{
	return (a*b)%mod;
}

const int mx = 200'000;

vll pow2(1 + mx);

vi children[1 + mx];
int N, M;

vi depth(1 + mx, 0);

vi A;

ll res = 0;

void dfs(int u)
{
	for(int v : children[u])
	{
		depth[v] = depth[u] + 1;
		dfs(v);
	}
}

void init(int N_, int M_, vi P_, vi A_)
{
	N = N_;
	M = M_;

	for(int i = 1; i < N+M; i++)
		children[P_[i]].push_back(i);

	dfs(0);

	A = vi(N, -1);
	for(int a : A_)
		A.push_back(a);

	pow2[0] = 1;
	for(int e = 1; e <= mx; e++)
		pow2[e] = mul(2, pow2[e-1]);

	// cerr << depth[1] << ' ' << depth[2] << '\n';

	for(int i = N; i < N+M; i++)
		res = ad(res, mul(A[i], pow2[N - depth[i]]));

	// cerr << "res = " << res << '\n';

	for(int f : A)
		cerr << f << '\n';
}

int count_ways(int L, int R)
{
	for(int i = L; i <= R; i++)
	{
		if(A[i] == 0)
		{
			// cerr << "activate " << i << "\n";
			A[i] = 1;
			res = ad(res, pow2[N - depth[i]]);
		}
		else
		{
			A[i] = 0;
			// cerr << "deactivate " << i << '\n';
			res = ad(res, mod - pow2[N - depth[i]]);
		}
	}

	return res;
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7296 KB	Output is correct
2	Correct	4 ms	7248 KB	Output is correct
3	Correct	7 ms	7376 KB	Output is correct
4	Correct	7 ms	7376 KB	Output is correct
5	Correct	7 ms	7376 KB	Output is correct
6	Correct	9 ms	7392 KB	Output is correct
7	Correct	8 ms	7396 KB	Output is correct
8	Correct	9 ms	7384 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7248 KB	Output is correct
2	Correct	6 ms	7376 KB	Output is correct
3	Correct	7 ms	7412 KB	Output is correct
4	Correct	8 ms	7376 KB	Output is correct
5	Correct	7 ms	7400 KB	Output is correct
6	Correct	8 ms	7420 KB	Output is correct
7	Correct	9 ms	7376 KB	Output is correct
8	Correct	11 ms	7444 KB	Output is correct
9	Correct	9 ms	7376 KB	Output is correct
10	Correct	9 ms	7476 KB	Output is correct
11	Correct	9 ms	7376 KB	Output is correct
12	Correct	9 ms	7432 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7296 KB	Output is correct
2	Correct	4 ms	7248 KB	Output is correct
3	Correct	7 ms	7376 KB	Output is correct
4	Correct	7 ms	7376 KB	Output is correct
5	Correct	7 ms	7376 KB	Output is correct
6	Correct	9 ms	7392 KB	Output is correct
7	Correct	8 ms	7396 KB	Output is correct
8	Correct	9 ms	7384 KB	Output is correct
9	Correct	5 ms	7248 KB	Output is correct
10	Correct	6 ms	7376 KB	Output is correct
11	Correct	7 ms	7412 KB	Output is correct
12	Correct	8 ms	7376 KB	Output is correct
13	Correct	7 ms	7400 KB	Output is correct
14	Correct	8 ms	7420 KB	Output is correct
15	Correct	9 ms	7376 KB	Output is correct
16	Correct	11 ms	7444 KB	Output is correct
17	Correct	9 ms	7376 KB	Output is correct
18	Correct	9 ms	7476 KB	Output is correct
19	Correct	9 ms	7376 KB	Output is correct
20	Correct	9 ms	7432 KB	Output is correct
21	Incorrect	9 ms	7420 KB	1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22	Halted	0 ms	0 KB	-

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	796 ms	9664 KB	Output is correct
2	Correct	1138 ms	11980 KB	Output is correct
3	Correct	1112 ms	11960 KB	Output is correct
4	Correct	1165 ms	11948 KB	Output is correct

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	796 ms	9664 KB	Output is correct
2	Correct	1138 ms	11980 KB	Output is correct
3	Correct	1112 ms	11960 KB	Output is correct
4	Correct	1165 ms	11948 KB	Output is correct
5	Execution timed out	3026 ms	9676 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7248 KB	Output is correct
2	Correct	6 ms	7376 KB	Output is correct
3	Correct	7 ms	7412 KB	Output is correct
4	Correct	8 ms	7376 KB	Output is correct
5	Correct	7 ms	7400 KB	Output is correct
6	Correct	8 ms	7420 KB	Output is correct
7	Correct	9 ms	7376 KB	Output is correct
8	Correct	11 ms	7444 KB	Output is correct
9	Correct	9 ms	7376 KB	Output is correct
10	Correct	9 ms	7476 KB	Output is correct
11	Correct	9 ms	7376 KB	Output is correct
12	Correct	9 ms	7432 KB	Output is correct
13	Correct	796 ms	9664 KB	Output is correct
14	Correct	1138 ms	11980 KB	Output is correct
15	Correct	1112 ms	11960 KB	Output is correct
16	Correct	1165 ms	11948 KB	Output is correct
17	Execution timed out	3026 ms	9676 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7296 KB	Output is correct
2	Correct	4 ms	7248 KB	Output is correct
3	Correct	7 ms	7376 KB	Output is correct
4	Correct	7 ms	7376 KB	Output is correct
5	Correct	7 ms	7376 KB	Output is correct
6	Correct	9 ms	7392 KB	Output is correct
7	Correct	8 ms	7396 KB	Output is correct
8	Correct	9 ms	7384 KB	Output is correct
9	Correct	5 ms	7248 KB	Output is correct
10	Correct	6 ms	7376 KB	Output is correct
11	Correct	7 ms	7412 KB	Output is correct
12	Correct	8 ms	7376 KB	Output is correct
13	Correct	7 ms	7400 KB	Output is correct
14	Correct	8 ms	7420 KB	Output is correct
15	Correct	9 ms	7376 KB	Output is correct
16	Correct	11 ms	7444 KB	Output is correct
17	Correct	9 ms	7376 KB	Output is correct
18	Correct	9 ms	7476 KB	Output is correct
19	Correct	9 ms	7376 KB	Output is correct
20	Correct	9 ms	7432 KB	Output is correct
21	Incorrect	9 ms	7420 KB	1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7296 KB	Output is correct
2	Correct	4 ms	7248 KB	Output is correct
3	Correct	7 ms	7376 KB	Output is correct
4	Correct	7 ms	7376 KB	Output is correct
5	Correct	7 ms	7376 KB	Output is correct
6	Correct	9 ms	7392 KB	Output is correct
7	Correct	8 ms	7396 KB	Output is correct
8	Correct	9 ms	7384 KB	Output is correct
9	Correct	5 ms	7248 KB	Output is correct
10	Correct	6 ms	7376 KB	Output is correct
11	Correct	7 ms	7412 KB	Output is correct
12	Correct	8 ms	7376 KB	Output is correct
13	Correct	7 ms	7400 KB	Output is correct
14	Correct	8 ms	7420 KB	Output is correct
15	Correct	9 ms	7376 KB	Output is correct
16	Correct	11 ms	7444 KB	Output is correct
17	Correct	9 ms	7376 KB	Output is correct
18	Correct	9 ms	7476 KB	Output is correct
19	Correct	9 ms	7376 KB	Output is correct
20	Correct	9 ms	7432 KB	Output is correct
21	Incorrect	9 ms	7420 KB	1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22	Halted	0 ms	0 KB	-

Submission #637190

Compilation message