oj.uz

Submission #1080750

# Submission time Handle Problem Language Result Execution time Memory
1080750 2024-08-29T13:41:02 Z LittleOrange Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 9048 KB 
#include "circuit.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000002022;
ll n,m;
vector<ll> p,a;
vector<vector<ll>> con;
vector<pair<ll,ll>> stat;
void dfs(ll);
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n=N;
  m=M;
  p.assign(P.begin(),P.end());
  a.assign(A.begin(),A.end());
  con.resize(n);
  for(ll i = 1;i<n+m;i++) con[p[i]].push_back(i);
  stat.resize(n+m);
  dfs(0);
}
void upd(ll i){
  if (i>=n){
    stat[i] = {a[i-n]==0,a[i-n]==1};
    return;
  }
  ll c = con[i].size();
  vector<ll> v(c+1,0),v0(c+1,0);
  v[0] = 1;
  for(ll j : con[i]){
    auto [x,y] = stat[j];
    for(ll i = 0;i<c;i++){
      v0[i] += v[i]*x%mod;
      v0[i+1] += v[i]*y%mod;
    }
    v.swap(v0);
    fill(v0.begin(),v0.end(),0);
  }
  ll x = 0, y = 0;
  for(ll j = 0;j<=c;j++){
    x += v[j]*(c-j)%mod;
    y += v[j]*j%mod;
  }
  stat[i] = {x%mod,y%mod};
}
void dfs(ll i){// 0, 1
  if(i<n) for(ll j : con[i]) dfs(j);
  upd(i);
}
int count_ways(int L, int R) {
  for(ll i = L;i<=R;i++) {
    a[i-n]^=1;
    ll x = i;
    upd(x);
    while (x){
      x = p[x];
      upd(x);
    }
  }
  return stat[0].second;
}

Subtask #1
0 / 2.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 Execution timed out 3086 ms 344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.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 Execution timed out 3086 ms 344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 4696 KB Output is correct
2 Correct 821 ms 9048 KB Output is correct
3 Correct 855 ms 9048 KB Output is correct
4 Correct 833 ms 9048 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 4696 KB Output is correct
2 Correct 821 ms 9048 KB Output is correct
3 Correct 855 ms 9048 KB Output is correct
4 Correct 833 ms 9048 KB Output is correct
5 Execution timed out 3048 ms 4828 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 500 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 86 ms 344 KB Output is correct
11 Correct 136 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 566 ms 4696 KB Output is correct
14 Correct 821 ms 9048 KB Output is correct
15 Correct 855 ms 9048 KB Output is correct
16 Correct 833 ms 9048 KB Output is correct
17 Execution timed out 3048 ms 4828 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.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 Execution timed out 3086 ms 344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.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 Execution timed out 3086 ms 344 KB Time limit exceeded
4 Halted 0 ms 0 KB -