Submission #1086290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086290		underwaterkillerwhale	Digital Circuit (IOI22_circuit)	C++17	22 / 100	910 ms	16984 KiB

circuit

//#include "circuit.h"

#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 2022;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 350;

int n, m, Q;
int P[N], a[N];
vector<int> ke[N];
pii qr[N];


bool sub4c = 0;

namespace sub3 {
    const int N1 = 2e3 + 7;
    ll dp[N1][2], f[N1][N1];

    void dfs (int u, int p) {
        iter (&v, ke[u]) {
            if (v != p) {///aware!!!!!!!!
                dfs(v, u);
            }
        }
        int m = SZ(ke[u]);
        rep (i, 0, m)
        rep (j, 0, m) f[i][j] = 0;
        f[0][0] = 1;
        rep (i, 1, m) {
            int v = ke[u][i - 1];
            rep (j, 0, m ) {
                f[i][j] = f[i - 1][j] * dp[v][0] % Mod;
                if (j) (f[i][j] += f[i - 1][j - 1] * dp[v][1] % Mod) %= Mod;
//                cout << u<<" "<<v<<","<<i<<" "<<j<<" "<<f[i][j] <<"\n";
            }
        }
        ll pre = f[m][0];
        rep (i, 1, m) {
            (dp[u][0] += pre) %= Mod;
            (pre += f[m][i]) %= Mod;
        }
        ll suf = 0;
        reb (i, m, 1) {
            (suf += f[m][i]) %= Mod;
            (dp[u][1] += suf) %= Mod;
        }
//        cout << u<<" "<<dp[u][0]<<","<<dp[u][1] <<"\n";
    }

    ll solution() {
        rep (i, 1, n + m) rep (j, 0, 1) dp[i][j] = 0;
        rep (i, n + 1, n + m) dp[i][a[i]] = 1;
        dfs(1, 0);
        return dp[1][1];
//        cout << dp[1][1] <<"\n";
    }
}

namespace sub4 {
    ll dp[N][2];
    int pa[N];

    bool check () {
        int K = 1; while (K < m) K *= 2;
        if (K == m && m == n + 1) {
            rep (i, 1, n + m - 1) if (P[i + 1] != (i - 1) / 2) return 0;
            return 1;
        }
        return 0;
    }

    void update (int u) {
        if (SZ(ke[u]) == 0) {
            dp[u][a[u]] = 1;
            dp[u][a[u] ^ 1] = 0;
            return;
        }
        int v1 = ke[u][0], v2 = ke[u][1];
        ll delta = (dp[v1][0] * dp[v2][1] % Mod + dp[v1][1] * dp[v2][0] % Mod) % Mod;
        dp[u][0] = (delta + 2LL * dp[v1][0] * dp[v2][0] % Mod) % Mod;
        dp[u][1] = (delta + 2LL * dp[v1][1] * dp[v2][1] % Mod) % Mod;
    }

    void dfs (int u, int p) {
        pa[u] = p;
        iter (&v, ke[u]) {
            dfs(v, u);
        }
        update (u);
    }

    void init () {
        dfs(1, 0);
    }

    int solution(int u) {
        while (u != 0) {
            update(u);
            u = pa[u];
        }
        return dp[1][1];
    }
}

int count_ways (int L, int R) {
    ++L;
    ++R;
    rep (i, L, R) a[i] ^= 1;
    if (n <= 1000 & m <= 1000)
        return sub3 :: solution();
    else if (L == R && sub4c)
        return sub4 :: solution(L);
}

void init (int _n, int _m, vector<int> _P, vector<int> _a) {
    n = _n;
    m = _m;
    rep (i, 1, n + m) P[i] = _P[i - 1];
    rep (i, 1, m) a[i + n] = _a[i - 1];
    rep (i, 1, n + m) {
        if (i > 1) {
            ke[P[i] + 1].pb(i);
//            cout << i <<" "<<P[i] + 1 <<"\n";
        }
    }
    sub4c = sub4 :: check();
    if (sub4c)
        sub4 :: init();
}

void solution() {
    cin >> n >> m >> Q;
    rep (i, 1, n + m) {
        cin >> P[i];
        if (i > 1) {
            ke[P[i] + 1].pb(i);
//            cout << i <<" "<<P[i] + 1 <<"\n";
        }
    }
    rep (i, n + 1, n + m) cin >> a[i];
    if (sub4 :: check())
        sub4 :: init();
    rep (i, 1, Q) {
        int L, R;
        cin >> L >> R;
        cout << count_ways(L, R) <<"\n";
    }
}

//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    init(3, 4, {-1, 0, 1, 2, 1, 1, 0}, {1, 0, 1, 0});
////    cout << count_ways(3, 4) <<"\n";
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug +5
3 4 3
-1 0 0 1 1 2 2
1 0 1 0
3 3
4 4
2 2
*/

Compilation message (stderr)

circuit.cpp:172:1: warning: multi-line comment [-Wcomment]
  172 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:131:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  131 |     if (n <= 1000 & m <= 1000)
      |         ~~^~~~~~~
circuit.cpp:135:1: warning: control reaches end of non-void function [-Wreturn-type]
  135 | }
      | ^

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11