oj.uz

답안 #683361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683361 2023-01-18T08:54:48 Z sunwukong123 디지털 회로 (IOI22_circuit) C++17
50 / 100
 1170 ms 53540 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 F[MAXN];
int state[MAXN];
int C[MAXN];
int sz[MAXN];
int choices[MAXN];
int n,m;

void pre(int x) {
    int S=V[x].size();
    if(V[x].size() != 0)sz[x] = 1;
    choices[x]=1;
    
    for(auto v:V[x]) {
      pre(v);
      sz[x]+=sz[v];
      choices[x]=choices[x]*choices[v]%MOD;
    }
    if(S)choices[x]=choices[x]*S%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) {
    db2(x,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;
    F[0]=1;
    FOR(i,1,n+m)F[i]=2*F[i-1]%MOD;
    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);
    dba(choices,0,n);
    seg=new node(0,m);
    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;
    db2(L,R);
    seg->update(L,R);
    return seg->sum;
}

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 5200 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 5 ms 5072 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5220 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct
10 Correct 3 ms 5456 KB Output is correct
11 Correct 3 ms 5456 KB Output is correct
12 Correct 3 ms 5200 KB Output is correct

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 5200 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 610 ms 13728 KB Output is correct
2 Correct 1022 ms 22432 KB Output is correct
3 Correct 1044 ms 22416 KB Output is correct
4 Correct 992 ms 22396 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 610 ms 13728 KB Output is correct
2 Correct 1022 ms 22432 KB Output is correct
3 Correct 1044 ms 22416 KB Output is correct
4 Correct 992 ms 22396 KB Output is correct
5 Correct 898 ms 13640 KB Output is correct
6 Correct 946 ms 22404 KB Output is correct
7 Correct 876 ms 22364 KB Output is correct
8 Correct 886 ms 22416 KB Output is correct
9 Correct 477 ms 5584 KB Output is correct
10 Correct 830 ms 6096 KB Output is correct
11 Correct 865 ms 6096 KB Output is correct
12 Correct 962 ms 6096 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 5 ms 5072 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5220 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct
10 Correct 3 ms 5456 KB Output is correct
11 Correct 3 ms 5456 KB Output is correct
12 Correct 3 ms 5200 KB Output is correct
13 Correct 610 ms 13728 KB Output is correct
14 Correct 1022 ms 22432 KB Output is correct
15 Correct 1044 ms 22416 KB Output is correct
16 Correct 992 ms 22396 KB Output is correct
17 Correct 898 ms 13640 KB Output is correct
18 Correct 946 ms 22404 KB Output is correct
19 Correct 876 ms 22364 KB Output is correct
20 Correct 886 ms 22416 KB Output is correct
21 Correct 477 ms 5584 KB Output is correct
22 Correct 830 ms 6096 KB Output is correct
23 Correct 865 ms 6096 KB Output is correct
24 Correct 962 ms 6096 KB Output is correct
25 Correct 1024 ms 31064 KB Output is correct
26 Correct 1135 ms 31520 KB Output is correct
27 Correct 1051 ms 31620 KB Output is correct
28 Correct 886 ms 31688 KB Output is correct
29 Correct 1170 ms 53456 KB Output is correct
30 Correct 876 ms 53540 KB Output is correct

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 5200 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 5200 KB 1st lines differ - on the 1st token, expected: '509', found: '3102'
4 Halted 0 ms 0 KB -