Submission #812867

#	Time	Username	Problem	Language	Result	Execution time	Memory
812867		blackyuki	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3020 ms	10000 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
const ll mod=1000002022;
#include "circuit.h"
vi a,b;
ll n,N_;
void init(int N, int M, std::vector<int> P, std::vector<int> A){
  N_=N;
  vvi ch(N+M);
  REP(i,1,N+M)ch[P[i]].pb(i);
  vi prod(N+M,1);
  for(ll i=N-1;i>=0;i--){
    prod[i]=ch[i].size();
    for(ll x:ch[i])prod[i]=prod[i]*prod[x]%mod;
  }
  vi dp(N+M,1);
  rep(i,N){
    vi tl(ch[i].size()+1,1),tr(ch[i].size()+1,1);
    rep(j,ch[i].size())tl[j+1]=tl[j]*prod[ch[i][j]]%mod;
    for(ll j=ch[i].size()-1;j>=0;j--)tr[j]=tr[j+1]*prod[ch[i][j]]%mod;
    rep(j,ch[i].size())dp[ch[i][j]]=dp[i]*tl[j]%mod*tr[j+1]%mod;
  }
  n=M;
  a=vi(n);b=vi(n);
  rep(i,n)a[i]=dp[N+i];
  rep(i,n)b[i]=A[i];
}

int count_ways(int L, int R) {
  ll l=L-N_,r=R+1-N_;
  REP(i,l,r)b[i]=1-b[i];
  ll ans=0;
  rep(i,n)ans+=a[i]*b[i];
  return ans%mod;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 28 / 28
• Subtask 8: 0 / 11