oj.uz

답안 #637190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637190 2022-08-31T21:50:31 Z blue 디지털 회로 (IOI22_circuit) C++17
13 / 100
 3000 ms 11980 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -