oj.uz

답안 #683395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683395 2023-01-18T10:17:34 Z sunwukong123 디지털 회로 (IOI22_circuit) C++17
0 / 100
 32 ms 26124 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD =  1'000'002'022;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 200005;
vector<int> V[MAXN];
int state[MAXN];
int C[MAXN];
int choices[MAXN];
int n,m;

void pre(int x) {
    int S=V[x].size();
    choices[x]=max(1ll,S);
    
    for(auto v:V[x]) {
      pre(v);
      choices[x]=choices[x]*choices[v]%MOD;
    }
}
void dfs(int x, int mult) {
  int S=V[x].size();
  if(S == 0) {
    C[x-n]=mult;
    return;
  }
  int pre[S+3]; 
  int suf[S+3];
  memset(pre, 0, sizeof pre);
  memset(suf, 0, sizeof suf);
  pre[0]=1;
  suf[S+1]=1;
  FOR(i,1,S) {
    int node = V[x][i-1];
    pre[i] = (pre[i-1] * choices[node]) % MOD;

  }
  DEC(i,S,1) {
    int node = V[x][i-1];
    suf[i] = (suf[i+1] * choices[node]) % MOD;
  }
  FOR(i,1,S) {
    int node = V[x][i-1];
    int mul = pre[i-1] * suf[i+1] % MOD;
    dfs(node, mult * mul % MOD);
  }

}

struct node {
  int s,e,m,pot,lazy,sum;
  node *l, *r;
  node (int _s, int _e) {
    s=_s;e=_e;m=(s+e)/2;
    if(s!=e){
      l=new node(s,m);
      r=new node(m+1,e);
      pot=(l->pot + r->pot)%MOD;
      sum = lazy = 0;
    } else {
      pot=C[s];
    }
  }
  void value() {
    if(lazy==0)return;
    sum=(MOD+(pot-sum)%MOD)%MOD;
    if(s==e){
      lazy=0;
      return;
    }
    l->lazy^=lazy;
    r->lazy^=lazy;
    lazy=0;
  }
  void update(int x, int y) {
   
    value();
    if(s==x&&e==y) {
      lazy=1;
      return;
    }
    if(x>m)r->update(x,y);
    else if(y<=m)l->update(x,y);
    else l->update(x,m), r->update(m+1,y);
    l->value(); r->value();
    sum = (l->sum + r->sum)%MOD;
  }
  int query(int x, int y) {
    value();
    if(s==x&&e==y) return sum;
    if(x>m)return r->query(x,y);
    else if(y<=m) return l->query(x,y);
    else return (l->query(x,m) + r->query(m+1,y))%MOD;
  } 
} *seg;

void init(int32_t n, int32_t m, vector<int32_t> P, vector<int32_t> A) {
    ::n=n;
    ::m=m;
   
    FOR(i,1,n+m-1) {
      V[P[i]].pb(i);
    }
    FOR(i,0,m-1) {
      state[i]=A[i];
    }
    pre(0);
    dfs(0,1);
    seg=new node(0,m);
    FOR(i,0,m-1){
      assert(C[i]==1);
    }
    FOR(i,0,m-1) {
      if(state[i])seg->update(i,i);
    }
}

int32_t count_ways(int32_t L, int32_t R) {
    L-=n;R-=n;
    seg->update(L,R);
    return seg->query(0,m-1);
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 3 ms 5168 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 7 ms 10064 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 3 ms 5168 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 26124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 26124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 7 ms 10064 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 3 ms 5168 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Incorrect 3 ms 5168 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -