oj.uz

Submission #1057304

# Submission time Handle Problem Language Result Execution time Memory
1057304 2024-08-13T16:52:30 Z esomer Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 3672 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1000002022;

int n;
vector<vector<int>> Adj;
vector<int> A;

pair<ll, ll> getAns(int x){
  int sz = (int)Adj[x].size();
  if(!sz){
    if(A[x-n]) return {1, 0};
    else return {0, 1};
  }
  vector<ll> ways(sz + 1, 0); ways[0] = 1;
  for(int node : Adj[x]){
    pair<ll, ll> w = getAns(node);
    for(int i = sz; i >= 0; i--){
      if(i+1 <= sz) ways[i+1] = (ways[i+1] + ways[i] * w.first) % MOD;
      ways[i] = (ways[i] * w.second) % MOD;
    }
  }
  // cout << "x " << x << endl;
  // for(int y : ways) cout << y << " ";
  // cout << endl;
  vector<ll> suf(sz+1, 0), pre(sz + 1, 0);
  pre[0] = ways[0];
  for(int i = 1; i <= sz; i++) pre[i] = (pre[i-1] + ways[i]) % MOD;
  suf[sz] = ways[sz];
  for(int i = sz - 1; i >= 0; i--) suf[i] = (suf[i+1] + ways[i]) % MOD;
  ll good = 0, bad = 0;
  for(int c = 1; c <= sz; c++){
    good += suf[c];
    bad += pre[c-1];
    good %= MOD; bad %= MOD;
  }
  // cout << "x " << x << " good " << good << " bad " << bad << "\n";
  return {good, bad};
}

void init(int N, int M, vector<int> P, vector<int> _A) {
  n = N;
  Adj.clear();
  Adj.resize(N+M);
  for(int i = 1; i < N + M; i++){
    Adj[P[i]].push_back(i);
  }
  A = _A;
}

int count_ways(int L, int R) {
  for(int i = L-n; i <= R-n; i++) A[i] ^= 1;
  // for(int i = 0; i < (int)A.size(); i++) cout << A[i] << " ";
  // cout << "\n";
  return (int)(getAns(0).first);
}

// mt19937 gen(time(0));

// int main(){
//   for(int h = 0; h < 10000; h++){    
//     int N = gen() % 5 + 1;
//     int M = gen() % 5 + 1;
//     vector<int> P(N+M);
//     P[0] = -1;
//     for(int i = 1; i < N + M; i++){
//       P[i] = gen() % min(i, N);
//     }
//     vector<int> A(M);
//     for(int i = 0; i < M; i++){
//       A[i] = gen() % 2;
//     }
//     init(N, M, P, A);
//     init2(N, M, P, A);
//     vector<pair<int, int>> queries;
//     int Q = gen() % 10 + 1;
//     bool bad = false;
//     while(Q--){
//       int R = gen() % M + 1;
//       int L = gen() % R + 1;
//       L--; R--; L += N; R += N;
//       queries.push_back({L, R});
//       if(count_ways(L, R) != count_ways2(L, R)){
//         bad = true;
//         break;
//       }
//     }
//     if(bad){
//       cout << N << " " << M << " " << (int)queries.size() << endl;
//       for(int x : P) cout << x << " "; cout << endl;
//       for(int x : A) cout << x << " "; cout << endl;
//       for(pair<int, int> p : queries) cout << p.first << " " << p.second << endl;
//       return 0;
//     }
//   }
// }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 500 KB Output is correct
4 Correct 13 ms 508 KB Output is correct
5 Correct 13 ms 344 KB Output is correct
6 Correct 13 ms 500 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 13 ms 504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 500 KB Output is correct
4 Correct 13 ms 508 KB Output is correct
5 Correct 13 ms 344 KB Output is correct
6 Correct 13 ms 500 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 13 ms 504 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 13 ms 344 KB Output is correct
30 Correct 13 ms 500 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 3 ms 344 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 15 ms 720 KB Output is correct
38 Correct 13 ms 600 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 4.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Execution timed out 3048 ms 3672 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 500 KB Output is correct
4 Correct 13 ms 508 KB Output is correct
5 Correct 13 ms 344 KB Output is correct
6 Correct 13 ms 500 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 13 ms 504 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 13 ms 344 KB Output is correct
30 Correct 13 ms 500 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 3 ms 344 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 15 ms 720 KB Output is correct
38 Correct 13 ms 600 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Execution timed out 3091 ms 600 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 500 KB Output is correct
4 Correct 13 ms 508 KB Output is correct
5 Correct 13 ms 344 KB Output is correct
6 Correct 13 ms 500 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 13 ms 504 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 13 ms 344 KB Output is correct
30 Correct 13 ms 500 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 3 ms 344 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 15 ms 720 KB Output is correct
38 Correct 13 ms 600 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Execution timed out 3048 ms 3672 KB Time limit exceeded
44 Halted 0 ms 0 KB -