oj.uz

Submission #1085305

# Submission time Handle Problem Language Result Execution time Memory
1085305 2024-09-07T23:11:54 Z underwaterkillerwhale Digital Circuit (IOI22_circuit) C++17
18 / 100
 484 ms 12548 KB 
#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 = 2e3 + 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];

namespace sub3 {
    ll dp[N][2], f[N][N];

    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);
    }

    ll 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 (L == R && sub4 :: check())
//        return sub4 :: solution(L);
//    else
        return sub3 :: solution();
}

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";
        }
    }
    if (sub4 :: check())
        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

circuit.cpp:167:1: warning: multi-line comment [-Wcomment]
  167 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 23 ms 11608 KB Output is correct
4 Correct 23 ms 12376 KB Output is correct
5 Correct 23 ms 12376 KB Output is correct
6 Correct 23 ms 12176 KB Output is correct
7 Correct 24 ms 12376 KB Output is correct
8 Correct 28 ms 12376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 23 ms 11608 KB Output is correct
4 Correct 23 ms 12376 KB Output is correct
5 Correct 23 ms 12376 KB Output is correct
6 Correct 23 ms 12176 KB Output is correct
7 Correct 24 ms 12376 KB Output is correct
8 Correct 28 ms 12376 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 26 ms 12376 KB Output is correct
30 Correct 23 ms 12376 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 5 ms 1624 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 24 ms 12548 KB Output is correct
38 Correct 23 ms 12376 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 600 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Runtime error 8 ms 2136 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 23 ms 11608 KB Output is correct
4 Correct 23 ms 12376 KB Output is correct
5 Correct 23 ms 12376 KB Output is correct
6 Correct 23 ms 12176 KB Output is correct
7 Correct 24 ms 12376 KB Output is correct
8 Correct 28 ms 12376 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 26 ms 12376 KB Output is correct
30 Correct 23 ms 12376 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 5 ms 1624 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 24 ms 12548 KB Output is correct
38 Correct 23 ms 12376 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 600 KB Output is correct
43 Runtime error 484 ms 812 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 23 ms 11608 KB Output is correct
4 Correct 23 ms 12376 KB Output is correct
5 Correct 23 ms 12376 KB Output is correct
6 Correct 23 ms 12176 KB Output is correct
7 Correct 24 ms 12376 KB Output is correct
8 Correct 28 ms 12376 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 26 ms 12376 KB Output is correct
30 Correct 23 ms 12376 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 5 ms 1624 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 24 ms 12548 KB Output is correct
38 Correct 23 ms 12376 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 600 KB Output is correct
43 Runtime error 8 ms 2136 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -