oj.uz

Submission #640366

# Submission time Handle Problem Language Result Execution time Memory
640366 2022-09-14T11:25:39 Z arnold518 Digital Circuit (IOI22_circuit) C++17
13 / 100
 3000 ms 30936 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const ll MOD = 1e9+2022;

int N, M;
vector<int> adj[MAXN+10];
ll phi[MAXN+10];
vector<ll> PV[MAXN+10], SV[MAXN+10];
int S[MAXN+10];
ll A[MAXN+10];

void dfs(int now)
{
    if(adj[now].empty())
    {
        phi[now]=1;
        return;
    }
    phi[now]=adj[now].size();
    for(auto nxt : adj[now])
    {
        dfs(nxt);
        PV[now].push_back(phi[nxt]);
        SV[now].push_back(phi[nxt]);
        phi[now]=phi[now]*phi[nxt]%MOD;
    }
    for(int i=1; i<PV[now].size(); i++) PV[now][i]=PV[now][i-1]*PV[now][i]%MOD;
    for(int i=SV[now].size()-2; i>=0; i--) SV[now][i]=SV[now][i+1]*SV[now][i]%MOD;
}

void dfs2(int now, ll val)
{
    if(adj[now].empty())
    {
        A[now]=val;
        return;
    }
    for(int i=0; i<adj[now].size(); i++)
    {
        int nxt=adj[now][i];
        ll t=1;
        if(i-1>=0) t=t*PV[now][i-1];
        if(i+1<SV[now].size()) t=t*SV[now][i+1];
        dfs2(nxt, val*t%MOD);
    }
}

ll ans=0;

void init(int _N, int _M, vector<int> _P, vector<int> _Q)
{
    N=_N; M=_M;
    for(int i=1; i<N+M; i++) adj[_P[i]].push_back(i);
    for(int i=N; i<N+M; i++) S[i]=_Q[i-N];

    dfs(0);
    dfs2(0, 1);
    
    for(int i=N; i<N+M; i++) if(S[i]) ans=(ans+A[i])%MOD;
    //for(int i=N; i<N+M; i++) printf("%lld ", A[i]); printf("\n");
}

int count_ways(int L, int R)
{
    for(int i=L; i<=R; i++)
    {
        if(S[i]) ans=(ans-A[i])%MOD;
        else ans=(ans+A[i])%MOD;
        if(ans<0) ans+=MOD;
        S[i]=!S[i];
    }
    return ans;
}

Compilation message

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=1; i<PV[now].size(); i++) PV[now][i]=PV[now][i-1]*PV[now][i]%MOD;
      |                  ~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void dfs2(int, ll)':
circuit.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0; i<adj[now].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
circuit.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(i+1<SV[now].size()) t=t*SV[now][i+1];
      |            ~~~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21456 KB Output is correct
2 Correct 11 ms 21328 KB Output is correct
3 Correct 11 ms 21456 KB Output is correct
4 Correct 11 ms 21456 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 13 ms 21480 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 13 ms 21404 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21328 KB Output is correct
2 Correct 11 ms 21456 KB Output is correct
3 Correct 11 ms 21504 KB Output is correct
4 Correct 11 ms 21456 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 14 ms 21492 KB Output is correct
7 Correct 12 ms 21584 KB Output is correct
8 Correct 12 ms 21568 KB Output is correct
9 Correct 11 ms 21584 KB Output is correct
10 Correct 11 ms 21660 KB Output is correct
11 Correct 11 ms 21584 KB Output is correct
12 Correct 11 ms 21456 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21456 KB Output is correct
2 Correct 11 ms 21328 KB Output is correct
3 Correct 11 ms 21456 KB Output is correct
4 Correct 11 ms 21456 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 13 ms 21480 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 13 ms 21404 KB Output is correct
9 Correct 10 ms 21328 KB Output is correct
10 Correct 11 ms 21456 KB Output is correct
11 Correct 11 ms 21504 KB Output is correct
12 Correct 11 ms 21456 KB Output is correct
13 Correct 11 ms 21456 KB Output is correct
14 Correct 14 ms 21492 KB Output is correct
15 Correct 12 ms 21584 KB Output is correct
16 Correct 12 ms 21568 KB Output is correct
17 Correct 11 ms 21584 KB Output is correct
18 Correct 11 ms 21660 KB Output is correct
19 Correct 11 ms 21584 KB Output is correct
20 Correct 11 ms 21456 KB Output is correct
21 Incorrect 11 ms 21456 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 26156 KB Output is correct
2 Correct 854 ms 30936 KB Output is correct
3 Correct 839 ms 30912 KB Output is correct
4 Correct 613 ms 30844 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 26156 KB Output is correct
2 Correct 854 ms 30936 KB Output is correct
3 Correct 839 ms 30912 KB Output is correct
4 Correct 613 ms 30844 KB Output is correct
5 Execution timed out 3028 ms 26192 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21328 KB Output is correct
2 Correct 11 ms 21456 KB Output is correct
3 Correct 11 ms 21504 KB Output is correct
4 Correct 11 ms 21456 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 14 ms 21492 KB Output is correct
7 Correct 12 ms 21584 KB Output is correct
8 Correct 12 ms 21568 KB Output is correct
9 Correct 11 ms 21584 KB Output is correct
10 Correct 11 ms 21660 KB Output is correct
11 Correct 11 ms 21584 KB Output is correct
12 Correct 11 ms 21456 KB Output is correct
13 Correct 525 ms 26156 KB Output is correct
14 Correct 854 ms 30936 KB Output is correct
15 Correct 839 ms 30912 KB Output is correct
16 Correct 613 ms 30844 KB Output is correct
17 Execution timed out 3028 ms 26192 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21456 KB Output is correct
2 Correct 11 ms 21328 KB Output is correct
3 Correct 11 ms 21456 KB Output is correct
4 Correct 11 ms 21456 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 13 ms 21480 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 13 ms 21404 KB Output is correct
9 Correct 10 ms 21328 KB Output is correct
10 Correct 11 ms 21456 KB Output is correct
11 Correct 11 ms 21504 KB Output is correct
12 Correct 11 ms 21456 KB Output is correct
13 Correct 11 ms 21456 KB Output is correct
14 Correct 14 ms 21492 KB Output is correct
15 Correct 12 ms 21584 KB Output is correct
16 Correct 12 ms 21568 KB Output is correct
17 Correct 11 ms 21584 KB Output is correct
18 Correct 11 ms 21660 KB Output is correct
19 Correct 11 ms 21584 KB Output is correct
20 Correct 11 ms 21456 KB Output is correct
21 Incorrect 11 ms 21456 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21456 KB Output is correct
2 Correct 11 ms 21328 KB Output is correct
3 Correct 11 ms 21456 KB Output is correct
4 Correct 11 ms 21456 KB Output is correct
5 Correct 11 ms 21456 KB Output is correct
6 Correct 13 ms 21480 KB Output is correct
7 Correct 11 ms 21456 KB Output is correct
8 Correct 13 ms 21404 KB Output is correct
9 Correct 10 ms 21328 KB Output is correct
10 Correct 11 ms 21456 KB Output is correct
11 Correct 11 ms 21504 KB Output is correct
12 Correct 11 ms 21456 KB Output is correct
13 Correct 11 ms 21456 KB Output is correct
14 Correct 14 ms 21492 KB Output is correct
15 Correct 12 ms 21584 KB Output is correct
16 Correct 12 ms 21568 KB Output is correct
17 Correct 11 ms 21584 KB Output is correct
18 Correct 11 ms 21660 KB Output is correct
19 Correct 11 ms 21584 KB Output is correct
20 Correct 11 ms 21456 KB Output is correct
21 Incorrect 11 ms 21456 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -