oj.uz

답안 #812511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
812511 2023-08-07T09:01:06 Z BT21tata 디지털 회로 (IOI22_circuit) C++17
18 / 100
 835 ms 13244 KB 
#include "circuit.h"
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
const ll MOD=1e9+2022;
const int N=2e5+5;
 
struct tree
{
    ll one, zero, lazy;
}t[4*N];
 
int nw[N], cnt, old[N], n, m;
ll suff[N], prv=1, a[N];
vector<int>g[N];
 
void dfs(int v)
{
    if(v>=n) return;
    old[cnt]=v;
    nw[v]=cnt++;
    for(int u : g[v])
        dfs(u);
}
 
void calc(int v, int p)
{
    if(v>=n)
    {
        a[v-n]=prv*suff[nw[p]+1];
        a[v-n]%=MOD;
        return;
    }
    
    for(int u : g[v])
        calc(u, v);
    
    prv*=(1ll*g[v].size());
    prv%=MOD;
}
 
void build(int v, int l, int r, vector<int>&state)
{
    if(l==r)
    {
        if(state[l]) t[v]={a[l], 0, 0};
        else t[v]={0, a[l], 0};
        return;
    }
    
    int mid=(l+r)>>1;
    build(v<<1, l, mid, state);
    build(v<<1|1, mid+1, r, state);
 
    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].zero+t[v<<1|1].zero)%MOD, 0};
}
 
void push(int v, int l, int r)
{
    swap(t[v].zero, t[v].one);
    t[v].lazy=0;
    if(l!=r)
    {
        t[v<<1].lazy^=1;
        t[v<<1|1].lazy^=1;
    }
}
 
void update(int v, int l, int r, int tl, int tr)
{
    if(t[v].lazy) push(v, l, r);
    if(r<tl or tr<l) return;
    if(tl<=l and r<=tr)
    {
        push(v, l, r);
        return;
    }
 
    int mid=(l+r)>>1;
    update(v<<1, l, mid, tl, tr);
    update(v<<1|1, mid+1, r, tl, tr);
 
    t[v]={(t[v<<1].one+t[v<<1|1].one)%MOD, (t[v<<1].zero+t[v<<1|1].zero)%MOD, 0};
}
 
void init(int N, int M, vector<int> p, vector<int> state)
{
    n=N; m=M;
    for(int i=1; i<n+m; i++)
        g[p[i]].push_back(i);
 
    dfs(0);
 
    suff[n]=1;
    for(int i=n-1; i>=0; i--)
    {
        suff[i]=1ll*suff[i+1]*g[old[i]].size();
        suff[i]%=MOD;
    }
 
    calc(0, -1);
 
    build(1, 0, m-1, state);
}
 
int count_ways(int l, int r)
{
    update(1, 0, m-1, l-n, r-n);
    return t[1].one;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 4916 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 2 ms 5072 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 2 ms 5072 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 321 ms 9092 KB Output is correct
2 Correct 835 ms 13196 KB Output is correct
3 Correct 626 ms 13200 KB Output is correct
4 Correct 589 ms 13128 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 321 ms 9092 KB Output is correct
2 Correct 835 ms 13196 KB Output is correct
3 Correct 626 ms 13200 KB Output is correct
4 Correct 589 ms 13128 KB Output is correct
5 Correct 604 ms 9112 KB Output is correct
6 Correct 830 ms 13192 KB Output is correct
7 Correct 744 ms 13244 KB Output is correct
8 Correct 499 ms 13192 KB Output is correct
9 Correct 413 ms 5200 KB Output is correct
10 Correct 701 ms 5456 KB Output is correct
11 Correct 703 ms 5456 KB Output is correct
12 Correct 628 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 4916 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 2 ms 5072 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 2 ms 5072 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 4916 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 2 ms 5072 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 2 ms 5072 KB Output is correct
11 Correct 2 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 2 ms 5072 KB Output is correct
14 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '706880838', found: '642305882'
15 Halted 0 ms 0 KB -