oj.uz

Submission #780512

# Submission time Handle Problem Language Result Execution time Memory
780512 2023-07-12T09:44:35 Z mousebeaver Digital Circuit (IOI22_circuit) C++17
16 / 100
 846 ms 6992 KB 
#define ll long long
#define pll pair<ll, ll>
#define MOD 1000002022
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

bool subFirst = false;
ll n = 0;
vector<ll> a(0);
vector<vector<ll>> adjlist(0);
pll dfsSubFirst(int i) //On, off
{
    if(adjlist[i].empty())
    {
        return {a[i], 1-a[i]};
    }

    ll c = adjlist[i].size();
    ll all = c;
    vector<ll> dp(c+1, 0); //Possibilities for being on
    dp[0] = 1;

    for(ll j : adjlist[i])
    {
        pll p = dfsSubFirst(j);
        all = (all * ((p.first+p.second)%MOD))%MOD;
        vector<ll> postdp(c+1, 0);
        for(ll k = 0; k <= c; k++)
        {
            postdp[k] = (dp[k]*p.second)%MOD;
            if(k > 0)
            {
                postdp[k] = (postdp[k] + (dp[k-1]*p.first)%MOD)%MOD;
            }
        }
        dp = postdp;
    }

    ll on = 0;
    for(ll k = c; k > 0; k--)
    {
        on = (on+((dp[k]*k)%MOD))%MOD;
    }

    return {on, (all+MOD-on)%MOD};
}

struct node
{
    ll on = 0;
    ll off = 0;
    bool flip = false;
    ll left = -1;
    ll right = -1;
};
vector<node> s(0);

void update(ll i)
{
    if(s[i].flip)
    {
        swap(s[i].on, s[i].off);
        if(s[i].left != -1)
        {
            s[s[i].left].flip = !s[s[i].left].flip;
            s[s[i].right].flip = !s[s[i].right].flip;
        }
        s[i].flip = false;
    }
}

void apply(ll i, ll L, ll R, ll a, ll b)
{
    if(L <= a && b <= R)
    {
        s[i].flip = !s[i].flip;
    }
    update(i);

    if(!(L <= a && b <= R) && !(R < a || b < L))
    {
        ll mid = (a+b)/2;
        apply(s[i].left, L, R, a, mid);
        apply(s[i].right, L, R, mid+1, b);

        ll l = s[i].left;
        ll r = s[i].right;

        s[i].on = (2*s[l].on*s[r].on)%MOD;
        s[i].on += (s[l].on*s[r].off)%MOD;
        s[i].on %= MOD;
        s[i].on += (s[l].off*s[r].on)%MOD;
        s[i].on %= MOD;

        s[i].off = (2*s[l].off*s[r].off)%MOD;
        s[i].off += (s[l].on*s[r].off)%MOD;
        s[i].off %= MOD;
        s[i].off += (s[l].off*s[r].on)%MOD;
        s[i].off %= MOD;
    }
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) 
{
    n = N+M;
    subFirst = (N <= 1000 && M <= 1000);
    subFirst = false;
    if(subFirst)
    {
        adjlist.assign(n, vector<ll> (0));
        for(ll i = 1; i < n; i++)
        {
            adjlist[P[i]].push_back(i);
        }
        a.assign(n, 0);
        for(ll i = N; i < n; i++)
        {
            a[i] = A[i-N];
        }
        return;
    }

    ll segnodes = n;
    node def;
    s.assign(segnodes, def);
    for(ll i = 1; i < segnodes; i++)
    {
        if((i-1)%2 == 0)
        {
            s[(i-1)/2].left = i;
        }
        else
        {
            s[(i-1)/2].right = i;
        }
    }
    for(ll i = 0; i < M; i++)
    {
        s[i+N].on = A[i];
        s[i+N].off = 1-s[i+N].on;
    }
    for(ll i = N-1; i >= 0; i--)
    {
        ll l = s[i].left;
        ll r = s[i].right;

        s[i].on = (2*s[l].on*s[r].on)%MOD;
        s[i].on += (s[l].on*s[r].off)%MOD;
        s[i].on %= MOD;
        s[i].on += (s[l].off*s[r].on)%MOD;
        s[i].on %= MOD;

        s[i].off = (2*s[l].off*s[r].off)%MOD;
        s[i].off += (s[l].on*s[r].off)%MOD;
        s[i].off %= MOD;
        s[i].off += (s[l].off*s[r].on)%MOD;
        s[i].off %= MOD;
    }
    return;
}

int count_ways(int L, int R) 
{
    if(subFirst)
    {
        for(ll i = L; i <= R; i++)
        {
            a[i] = 1-a[i];
        }
        return dfsSubFirst(0).first;
    }

    ll segnodes = s.size();
    ll M = (segnodes+1)/2;
    apply(0, L+1-M, R+1-M, 0, M-1);
    return s[0].on;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '33'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Runtime error 1 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '33'
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 3624 KB Output is correct
2 Correct 766 ms 6956 KB Output is correct
3 Correct 547 ms 6948 KB Output is correct
4 Correct 670 ms 6948 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 3624 KB Output is correct
2 Correct 766 ms 6956 KB Output is correct
3 Correct 547 ms 6948 KB Output is correct
4 Correct 670 ms 6948 KB Output is correct
5 Correct 713 ms 3536 KB Output is correct
6 Correct 698 ms 6992 KB Output is correct
7 Correct 846 ms 6964 KB Output is correct
8 Correct 767 ms 6856 KB Output is correct
9 Correct 330 ms 464 KB Output is correct
10 Correct 772 ms 720 KB Output is correct
11 Correct 687 ms 716 KB Output is correct
12 Correct 434 ms 592 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Runtime error 1 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '33'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '33'
3 Halted 0 ms 0 KB -