oj.uz

답안 #812250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
812250 2023-08-07T08:00:44 Z BT21tata 디지털 회로 (IOI22_circuit) C++17
18 / 100
 853 ms 13228 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(!g[v].size()) return;
    old[cnt]=v;
    nw[v]=cnt++;
    for(int u : g[v])
        dfs(u);
}

void calc(int v, int p)
{
    if(!g[v].size())
    {
        a[v-n]=prv*suff[nw[p]+1];
        a[v-n]%=MOD;
        return;
    }
    
    for(int u : g[v])
        calc(u, v);
    
    prv*=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)
    {
        t[v].lazy=1;
        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]=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 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 5072 KB Output is correct
8 Correct 2 ms 5072 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 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 Incorrect 2 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 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 2 ms 5072 KB Output is correct
8 Correct 2 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 3 ms 5072 KB Output is correct
14 Incorrect 2 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 459 ms 9040 KB Output is correct
2 Correct 792 ms 13192 KB Output is correct
3 Correct 780 ms 13192 KB Output is correct
4 Correct 641 ms 13228 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 459 ms 9040 KB Output is correct
2 Correct 792 ms 13192 KB Output is correct
3 Correct 780 ms 13192 KB Output is correct
4 Correct 641 ms 13228 KB Output is correct
5 Correct 703 ms 9040 KB Output is correct
6 Correct 699 ms 13128 KB Output is correct
7 Correct 853 ms 13188 KB Output is correct
8 Correct 757 ms 13188 KB Output is correct
9 Correct 288 ms 5200 KB Output is correct
10 Correct 628 ms 5456 KB Output is correct
11 Correct 739 ms 5456 KB Output is correct
12 Correct 528 ms 5456 KB Output is correct

Subtask #6
0 / 27.0

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