oj.uz

답안 #1057981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057981 2024-08-14T07:49:11 Z aykhn 디지털 회로 (IOI22_circuit) C++17
7 / 100
 3000 ms 13908 KB 
#include <bits/stdc++.h>
#include "circuit.h"
 
using namespace std;
 
#define int long long
 
const int MXN = 2e5 + 5;
const int mod = 1e9 + 2022;
 
int n, m, res = 0;
vector<int> A, P;
vector<int> adj[MXN];
int dp[2][MXN], SZ[MXN];
int cnt = 0;
 
void calc(int a)
{
  dp[0][a] = dp[1][a] = 0;
  if (adj[a].empty())
  {
    dp[0][a] = A[a] ^ 1;
    dp[1][a] = A[a];
    return;
  }
  int sz = adj[a].size();
  vector<int> dp1(sz + 1, 0);
  dp1[0] = 1;
  for (int &v : adj[a])
  {
    for (int i = sz; i >= 0; i--)
    {
      dp1[i] = (dp1[i] * dp[0][v]) % mod;
      if (i) dp1[i] = (dp1[i] + ((dp1[i - 1] * dp[1][v]) % mod)) % mod;
    }
  }
  for (int i = 0; i <= sz; i++)
  {
    dp[0][a] = (dp[0][a] + (((sz - i) * dp1[i]) % mod)) % mod;
    dp[1][a] = (dp[1][a] +  ((i * dp1[i]) % mod)) % mod;
  }
}
 
void dfs(int a)
{
  for (int &v : adj[a])
  {
    dfs(v);
  }
  calc(a);
}

int val[MXN];
 
void init(int32_t N, int32_t M, vector<int32_t> PP, vector<int32_t> AA) 
{
  n = N, m = M;
  for (int32_t &i : PP) P.push_back(i);
  for (int32_t &i : AA) A.push_back(i);
  reverse(A.begin(), A.end());
  A.resize(N + M, 0);
  reverse(A.begin(), A.end());
  for (int i = 1; i < N + M; i++) adj[P[i]].push_back(i);
  for (int i = N; i < N + M; i++)
  {
    int prev = A[i];
    A[i] = 0;
    dfs(0);
    int org = dp[1][0];
    A[i] = 1;
    dfs(0);
    val[i] = (dp[1][0] - org + mod) % mod;
    A[i] = prev;
  }
}
 
int32_t count_ways(int32_t L, int32_t R) {
  for (int i = L; i <= R; i++) A[i] ^= 1;
  int res = 0;
  for (int i = n; i < n + m; i++)
  {
    res = (res + A[i] * val[i]) % mod;
  }
  return res;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9048 KB Output is correct
3 Execution timed out 3043 ms 9048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 8 ms 9048 KB Output is correct
3 Correct 32 ms 9048 KB Output is correct
4 Correct 29 ms 9048 KB Output is correct
5 Correct 29 ms 9220 KB Output is correct
6 Correct 61 ms 9048 KB Output is correct
7 Correct 116 ms 9048 KB Output is correct
8 Correct 128 ms 9236 KB Output is correct
9 Correct 128 ms 9048 KB Output is correct
10 Correct 112 ms 9048 KB Output is correct
11 Correct 111 ms 9048 KB Output is correct
12 Correct 79 ms 9224 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9048 KB Output is correct
3 Execution timed out 3043 ms 9048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3013 ms 13908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3013 ms 13908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 8 ms 9048 KB Output is correct
3 Correct 32 ms 9048 KB Output is correct
4 Correct 29 ms 9048 KB Output is correct
5 Correct 29 ms 9220 KB Output is correct
6 Correct 61 ms 9048 KB Output is correct
7 Correct 116 ms 9048 KB Output is correct
8 Correct 128 ms 9236 KB Output is correct
9 Correct 128 ms 9048 KB Output is correct
10 Correct 112 ms 9048 KB Output is correct
11 Correct 111 ms 9048 KB Output is correct
12 Correct 79 ms 9224 KB Output is correct
13 Execution timed out 3013 ms 13908 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9048 KB Output is correct
3 Execution timed out 3043 ms 9048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9048 KB Output is correct
3 Execution timed out 3043 ms 9048 KB Time limit exceeded
4 Halted 0 ms 0 KB -