oj.uz

답안 #1068701

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068701 2024-08-21T11:24:50 Z beaconmc 디지털 회로 (IOI22_circuit) C++17
2 / 100
 449 ms 16216 KB 
    #include <bits/stdc++.h>
     
    typedef int ll;
    using namespace std;
     
     
    #define FOR(i, x, y) for(ll i=x; i<y; i++)
    #define FORNEG(i, x, y) for(ll i=x; i>y; i--)
    #define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
     
     
    basic_string<ll> edges[200001];
    ll possible[200001];
    ll contrib[200001];
    ll dps[200001];
    vector<int> p;
     
     
     
     
    int initdfs(ll a){
      if (edges[a].size() == 0) return possible[a] = 1;
     
      ll temp = 1;
      for (auto&i : edges[a]){
        temp *= initdfs(i);
        temp %= 1000002022;
      }
      temp *= edges[a].size();
      temp %= 1000002022;
     
     
      return possible[a] = temp;
    }
     
    int dp(ll a){
      if (a==0) return 1;
      if (dps[a] != -1) return dps[a];
     
      ll temp = 1;
     
      for (auto&i : edges[p[a]]){
        if (i != a) temp *= possible[i];
        temp %= 1000002022;
      }
      dps[a] = temp * dp(p[a]) % 1000002022;
      return dps[a];
    }
     
    ll n,m;
     
     
     
    const ll NN = (1<<18);
    ll tree[NN*2];
    ll actual[NN*2];
    ll lazy[NN*2];
     
    int actupd(ll a, ll b, ll val, ll k=1, ll x = 0, ll y = NN-1){
     
      if (b<x || a>y) return actual[k];
      if (a<=x && y<=b){
     
        actual[k] += val;
        actual[k] %= 1000002022;
        return actual[k];
      }
      ll mid = (x+y)/2;
     
     
      actual[k] =  actupd(a,b,val,k*2, x, mid) + actupd(a,b,val,k*2+1, mid+1, y);
      actual[k] %= 1000002022;
     
      return actual[k];
    }
     
     
    void prop(ll k){
      lazy[k*2] += lazy[k];
      lazy[k*2+1] += lazy[k];
      if (lazy[k] %2==1){
        tree[k] = (actual[k] - tree[k]+1000002022)%1000002022;
      }
      lazy[k] = 0;
    }
     
     
    int upd(ll a, ll b, ll k=1, ll x = 0, ll y = NN-1){
      if (b<x || a>y) return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
      if (a<=x && y<=b){
        lazy[k] += 1;
        return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
      }
      ll mid = (x+y)/2;
      prop(k);
     
      tree[k] = upd(a,b,k*2, x, mid) + upd(a,b,k*2+1, mid+1, y);
      tree[k] %= 1000002022;
      return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
    }
     
    void init(int N, int M, std::vector<int> P, std::vector<int> A) {
      FOR(i,0,200001) dps[i] = -1;
      FOR(i,0,NN*2) tree[i] = 0, actual[i] = 0, lazy[i] = 0;
      p = P;
      n = N;
      m = M;
      FOR(i,1,N+M){
        edges[P[i]].push_back(i);
      }
      initdfs(0);
     
     
      FOR(i,N,N+M){
        ll temp = possible[i];
        temp *= dp(i);
        contrib[i] = temp%1000002022;
      }
      FOR(i,n,n+m){
        actupd(i-n+1, i-n+1, contrib[i]);
      }
      FOR(i,0,NN*2) tree[i] = actual[i];
      FOR(i,n,n+m){
        if (A[i-n] == 0){
          upd(i-n+1, i-n+1);
        }
      }
     
     
    }
     
     
     
     
     
    int count_ways(int L, int R) {
      upd(L-n+1, R-n+1);
     
     
      return lazy[1]%2==0 ? tree[1] : ((actual[1] - tree[1]+1000002022)%1000002022);
     
    }

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15192 KB Output is correct
2 Correct 2 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 8 ms 15192 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 8 ms 15228 KB Output is correct
7 Correct 8 ms 15192 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15192 KB Output is correct
2 Correct 2 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 8 ms 15192 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 8 ms 15228 KB Output is correct
7 Correct 8 ms 15192 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct
9 Correct 2 ms 15192 KB Output is correct
10 Incorrect 2 ms 15192 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-391035600'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 449 ms 16216 KB 1st lines differ - on the 1st token, expected: '431985922', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 449 ms 16216 KB 1st lines differ - on the 1st token, expected: '431985922', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15192 KB Output is correct
2 Correct 2 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 8 ms 15192 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 8 ms 15228 KB Output is correct
7 Correct 8 ms 15192 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct
9 Correct 2 ms 15192 KB Output is correct
10 Incorrect 2 ms 15192 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-391035600'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15192 KB Output is correct
2 Correct 2 ms 15192 KB Output is correct
3 Correct 7 ms 15192 KB Output is correct
4 Correct 8 ms 15192 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 8 ms 15228 KB Output is correct
7 Correct 8 ms 15192 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct
9 Correct 2 ms 15192 KB Output is correct
10 Incorrect 2 ms 15192 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-391035600'
11 Halted 0 ms 0 KB -