oj.uz

Submission #855916

# Submission time Handle Problem Language Result Execution time Memory
855916 2023-10-02T09:09:46 Z onepunchac168 Digital Circuit (IOI22_circuit) C++17
46 / 100
 3000 ms 9600 KB 
//------------------------------------\\
//   ------------------------------   \\
//  |  created by Dinh Manh Hung   |  \\
//  |      tht.onepunchac168       |  \\
//  |     THPT CHUYEN HA TINH      |  \\
//  |      HA TINH, VIET NAM       |  \\
//  |           Siuuu              |  \\
//   ------------------------------   \\
//------------------------------------\\

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

#define            task     ""
#define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define             ldb     long double
#define              pb     push_back
#define              eb     emplace_back
#define              fi     first
#define              se     second
#define           all(x)    begin(x),end(x)
#define       uniquev(v)    v.resize(unique(all(v))-v.begin())
#define       rep(i,a,b)    for (int i=a;i<=b;i++)
#define        cntbit(v)    __builtin_popcountll(v)
#define         gcd(a,b)    __gcd(a,b)
#define         lcm(a,b)    ((1LL*a*b)/__gcd(a,b))
#define          mask(x)    (1LL<<(x))
#define     readbit(x,i)    ((x>>i)&1)
#define             Yes     cout << "Yes"
#define             YES     cout << "YES"
#define              No     cout << "No"
#define              NO     cout << "NO"

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const ll mod=1000002022;
const char nl = '\n';

inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = (xo<<1) + (xo<<3) + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}

// DEBUG
/*
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
*/

/* END OF TEMPLATE*/

// ================= Solution =================//

/*
void onepunchac168();

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    file(task);
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--)
    {
        onepunchac168();
    }
}

void onepunchac168()
{

}
*/
const int Na=1e5+5;
int n,m,q;
int p[Na*2];
int a[Na];
vector <int> vt[Na*2];
ll dp[2*Na];
void dfs(int u)
{
    dp[u]=1;
    if (vt[u].empty())
    {
        return;
    }
    for (auto v:vt[u])
    {
        dfs(v);
        dp[u]=(dp[u]*dp[v])%mod;
    }
    dp[u]=(dp[u]*ll((vt[u]).size()))%mod;
}
ll dpa[Na];
void dfsa(int u,ll val)
{
    if (u>n)
    {
        dpa[u-n]=val;
        return;
    }
    vector <ll> pref(int(vt[u].size())+2),suff(int(vt[u].size())+2);
    pref[0]=1;
    suff[int(vt[u].size())+1]=1;
    for (int i=1;i<=int(vt[u].size());i++)
    {
        pref[i]=(pref[i-1]*dp[vt[u][i-1]])%mod;
    }
    for (int i=int(vt[u].size());i>=1;i--)
    {
        suff[i]=(suff[i+1]*dp[vt[u][i-1]])%mod;
    }
    for (int i=1;i<=int(vt[u].size());i++)
    {
        ll cost=val;
        cost=(cost*pref[i-1])%mod;
        cost=(cost*suff[i+1])%mod;
        dfsa(vt[u][i-1],cost);
    }
}
bool check[Na];
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n=N;
    m=M;
    for (int i=0;i<P.size();i++)
    {
        p[i+1]=P[i]+1;
    }
    for (int i=0;i<A.size();i++)
    {
        a[i+1]=A[i];
    }
    for (int i=1;i<=m;i++)
    {
        check[i]=a[i];
    }
    for (int i=1;i<=n+m;i++)
    {
        if (p[i]==0)
        {
            continue;
        }
        vt[p[i]].pb(i);
    }
    dfs(1);
    dfsa(1,1);
}

int count_ways(int L, int R)
{
    L++;
    R++;
    L-=n;
    R-=n;
    for (int i=L;i<=R;i++)
    {
        check[i]=1-check[i];
    }
    ll res=0;
    for (int i=1;i<=m;i++)
    {
        if (check[i]==0)
        {
            continue;
        }
        res=(res+dpa[i])%mod;
    }
    return res;
}

// goodbye see ya

Compilation message

circuit.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\\
      | ^
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for (int i=0;i<P.size();i++)
      |                  ~^~~~~~~~~
circuit.cpp:180:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |     for (int i=0;i<A.size();i++)
      |                  ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7508 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7508 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7604 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7508 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7508 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7604 KB Output is correct
19 Correct 2 ms 7512 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 2 ms 7256 KB Output is correct
23 Correct 2 ms 7256 KB Output is correct
24 Correct 2 ms 7256 KB Output is correct
25 Correct 2 ms 7256 KB Output is correct
26 Correct 2 ms 7256 KB Output is correct
27 Correct 3 ms 7508 KB Output is correct
28 Correct 2 ms 7256 KB Output is correct
29 Correct 2 ms 7256 KB Output is correct
30 Correct 2 ms 7256 KB Output is correct
31 Correct 2 ms 7512 KB Output is correct
32 Correct 2 ms 7472 KB Output is correct
33 Correct 2 ms 7256 KB Output is correct
34 Correct 2 ms 7256 KB Output is correct
35 Correct 2 ms 7256 KB Output is correct
36 Correct 2 ms 7608 KB Output is correct
37 Correct 2 ms 7512 KB Output is correct
38 Correct 2 ms 7512 KB Output is correct
39 Correct 2 ms 7256 KB Output is correct
40 Correct 2 ms 7256 KB Output is correct
41 Correct 2 ms 7256 KB Output is correct
42 Correct 2 ms 7256 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 9600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 9600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7508 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7604 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Execution timed out 3052 ms 9600 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7508 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7508 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7604 KB Output is correct
19 Correct 2 ms 7512 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 2 ms 7256 KB Output is correct
23 Correct 2 ms 7256 KB Output is correct
24 Correct 2 ms 7256 KB Output is correct
25 Correct 2 ms 7256 KB Output is correct
26 Correct 2 ms 7256 KB Output is correct
27 Correct 3 ms 7508 KB Output is correct
28 Correct 2 ms 7256 KB Output is correct
29 Correct 2 ms 7256 KB Output is correct
30 Correct 2 ms 7256 KB Output is correct
31 Correct 2 ms 7512 KB Output is correct
32 Correct 2 ms 7472 KB Output is correct
33 Correct 2 ms 7256 KB Output is correct
34 Correct 2 ms 7256 KB Output is correct
35 Correct 2 ms 7256 KB Output is correct
36 Correct 2 ms 7608 KB Output is correct
37 Correct 2 ms 7512 KB Output is correct
38 Correct 2 ms 7512 KB Output is correct
39 Correct 2 ms 7256 KB Output is correct
40 Correct 2 ms 7256 KB Output is correct
41 Correct 2 ms 7256 KB Output is correct
42 Correct 2 ms 7256 KB Output is correct
43 Correct 862 ms 7512 KB Output is correct
44 Correct 1114 ms 7768 KB Output is correct
45 Correct 1193 ms 7512 KB Output is correct
46 Correct 1489 ms 7768 KB Output is correct
47 Correct 1992 ms 7768 KB Output is correct
48 Correct 1977 ms 7768 KB Output is correct
49 Correct 1969 ms 7768 KB Output is correct
50 Correct 1548 ms 7764 KB Output is correct
51 Correct 2213 ms 7692 KB Output is correct
52 Correct 1992 ms 7692 KB Output is correct
53 Correct 495 ms 8536 KB Output is correct
54 Correct 2023 ms 7768 KB Output is correct
55 Correct 1978 ms 7512 KB Output is correct
56 Correct 1964 ms 7512 KB Output is correct
57 Correct 1955 ms 7512 KB Output is correct
58 Correct 1969 ms 8792 KB Output is correct
59 Correct 1991 ms 8792 KB Output is correct
60 Correct 2210 ms 8792 KB Output is correct
61 Correct 1051 ms 7768 KB Output is correct
62 Correct 1441 ms 7512 KB Output is correct
63 Correct 1492 ms 7512 KB Output is correct
64 Correct 1967 ms 7512 KB Output is correct
65 Correct 502 ms 7512 KB Output is correct
66 Correct 1635 ms 7764 KB Output is correct
67 Correct 1580 ms 7512 KB Output is correct
68 Correct 1619 ms 7512 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7508 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7508 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7604 KB Output is correct
19 Correct 2 ms 7512 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 2 ms 7256 KB Output is correct
23 Correct 2 ms 7256 KB Output is correct
24 Correct 2 ms 7256 KB Output is correct
25 Correct 2 ms 7256 KB Output is correct
26 Correct 2 ms 7256 KB Output is correct
27 Correct 3 ms 7508 KB Output is correct
28 Correct 2 ms 7256 KB Output is correct
29 Correct 2 ms 7256 KB Output is correct
30 Correct 2 ms 7256 KB Output is correct
31 Correct 2 ms 7512 KB Output is correct
32 Correct 2 ms 7472 KB Output is correct
33 Correct 2 ms 7256 KB Output is correct
34 Correct 2 ms 7256 KB Output is correct
35 Correct 2 ms 7256 KB Output is correct
36 Correct 2 ms 7608 KB Output is correct
37 Correct 2 ms 7512 KB Output is correct
38 Correct 2 ms 7512 KB Output is correct
39 Correct 2 ms 7256 KB Output is correct
40 Correct 2 ms 7256 KB Output is correct
41 Correct 2 ms 7256 KB Output is correct
42 Correct 2 ms 7256 KB Output is correct
43 Execution timed out 3052 ms 9600 KB Time limit exceeded
44 Halted 0 ms 0 KB -