oj.uz

답안 #1057354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057354 2024-08-13T17:51:36 Z sofijavelkovska 디지털 회로 (IOI22_circuit) C++17
18 / 100
 613 ms 15932 KB 
#include "circuit.h"
//#include "stub.cpp"

#include <bits/stdc++.h>
using namespace std;

const int MOD=1000002022, MAXN=(1<<17);

int n, m;
vector<int> parent, a;
vector<int> adj[MAXN];
int subtree[2*MAXN];
long long factor[2*MAXN];
long long ones[2*MAXN-1], zeros[2*MAXN-1];
int lazy[2*MAXN-1]={0};

long long power(long long n, long long k)
{
    long long result=1, mul=n;
    for (int i=0; i<32; i++)
    {
        if (k&(1<<i))
            result=result*mul%MOD;
        mul=mul*mul%MOD;
    }

    return result;
}

void calcsize(int x)
{
    if (x>=n)
        subtree[x]=0;
    else
        subtree[x]=1;
    for (auto y : adj[x])
    {
        calcsize(y);
        subtree[x]=subtree[x]+subtree[y];
    }

    return;
}

void calcfactor(int x, long long current)
{
    if (x!=0)
        current=current*power(2, subtree[x])%MOD;
    factor[x]=current;
    for (auto y : adj[x])
        calcfactor(y, current);

    return;
}

void propagate(int x, int l, int r)
{
    if (r-l==1)
    {
        lazy[x]=0;
        return;
    }
    if (lazy[x]==0)
        return;
    swap(ones[2*x+1], zeros[2*x+1]);
    swap(ones[2*x+2], zeros[2*x+2]);
    lazy[2*x+1]=(lazy[2*x+1]+1)%2;
    lazy[2*x+2]=(lazy[2*x+2]+1)%2;
    lazy[x]=0;

    return;
}

void update(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return;
    if (l>=lt && r<=rt)
    {
        swap(ones[x], zeros[x]);
        lazy[x]=(lazy[x]+1)%2;
        return;
    }
    propagate(x, l, r);
    update(2*x+1, l, (l+r)/2, lt, rt);
    update(2*x+2, (l+r)/2, r, lt, rt);
    ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
    zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;

    return;
}

void buildtree(int x, int l, int r)
{
    if (r-l==1)
    {
        if (l>=m)
        {
            ones[x]=0;
            zeros[x]=0;
            return;
        }
        if (a[l]==1)
        {
            ones[x]=factor[l+n];
            zeros[x]=0;
        }
        else
        {
            ones[x]=0;
            zeros[x]=factor[l+n];
        }
        return;
    }
    buildtree(2*x+1, l, (l+r)/2);
    buildtree(2*x+2, (l+r)/2, r);
    ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
    zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;

    return;
}

void init(int N, int M, vector<int> P, vector<int> A)
{
    n=N;
    m=M;
    parent=P;
    a=A;
    for (int i=1; i<n+m; i++)
        adj[parent[i]].push_back(i);
    calcsize(0);
    calcfactor(0, 1);
    buildtree(0, 0, MAXN);

    return;
}

int count_ways(int l, int r)
{
    l=l-n;
    r=r-n;
    update(0, 0, MAXN, l, r+1);

    return ones[0];
}

Subtask #1
2.0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 13656 KB Output is correct
2 Correct 597 ms 15696 KB Output is correct
3 Correct 603 ms 15932 KB Output is correct
4 Correct 538 ms 15704 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 13656 KB Output is correct
2 Correct 597 ms 15696 KB Output is correct
3 Correct 603 ms 15932 KB Output is correct
4 Correct 538 ms 15704 KB Output is correct
5 Correct 475 ms 13656 KB Output is correct
6 Correct 582 ms 15704 KB Output is correct
7 Correct 606 ms 15912 KB Output is correct
8 Correct 613 ms 15704 KB Output is correct
9 Correct 278 ms 11608 KB Output is correct
10 Correct 560 ms 11608 KB Output is correct
11 Correct 561 ms 11608 KB Output is correct
12 Correct 575 ms 11608 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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