oj.uz

Submission #728645

# Submission time Handle Problem Language Result Execution time Memory
728645 2023-04-22T18:58:52 Z grogu Digital Circuit (IOI22_circuit) C++17
0 / 100
 9 ms 2148 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define here cerr<<"==============================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define popb pop_back
#define all(x_) x_.begin(), x_.end()

using namespace std;
#define mod 1000002022
ll add(ll x,ll y){
    x+=y;
    x%=mod;
    if(x<0) x+=mod;
    return x;
}
ll mul(ll x,ll y){
    x*=y;
    x%=mod;
    if(x<0) x+=mod;
    return x;
}
#define maxn 1005
int n,m;
int par[maxn];
int a[maxn];
int deg[maxn];
vector<int> g[maxn];
vector<int> v[maxn];
vector<int> topo;
void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    m = M;
    for(int i = 1;i<n+m;i++){
        par[i+1] = P[i]+1;
        g[i+1].pb(P[i]+1);
        v[P[i]+1].pb(i+1);
        deg[P[i]+1]++;
    }
    for(int i = n;i<n+m;i++) a[i+1] = A[i-n];
    queue<int> q;
    for(int i = 1;i<=n+m;i++) if(!deg[i]) q.push(i);
    while(q.size()){
        int u = q.front();
        q.pop();
        if(u<=n) topo.pb(u);
        for(int s : g[u]){
            deg[s]--;
            if(!deg[s]) q.push(s);
        }
    }
}
ll dp[maxn];
ll sum[maxn][maxn];
int count_ways(int L, int R){
    L++; R++;
    for(int i = L;i<=R;i++) a[i]^=1;
    for(int i = n+1;i<=n+m;i++) dp[i] = a[i];
    for(int u : topo){
        int sz = v[u].size();
        for(int i = 0;i<=sz;i++) for(int j = 1;j<=sz;j++) sum[i][j] = 0;
        for(int i = 0;i<=sz;i++) sum[i][0] = 1;
        dp[u] = 0;
        for(int k = 1;k<=sz;k++){
            for(int j = 1;j<=sz;j++){
                ll val = dp[v[u][j-1]];
                sum[j][k] = add(sum[j-1][k],mul(sum[j-1][k-1],val));
            }
            dp[u] = add(dp[u],sum[sz][k]);
        }
    }

    return dp[1];
}
/**
3 4 2
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
**/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 2nd lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 2nd lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 2nd lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2148 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 9 ms 2148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 2nd lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 2nd lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 2nd lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -