oj.uz

답안 #720972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
720972 2023-04-10T00:48:08 Z lam 디지털 회로 (IOI22_circuit) C++17
0 / 100
 689 ms 8180 KB 
#include "circuit.h"

#include <vector>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll> ii;
#define ff first
#define ss second
const int maxn = 2e5 + 10;
const ll mod =  1000002022LL;
int n,m;
int a[maxn];
vector <int> adj[maxn];
ll s[maxn],dp[maxn],sdp[maxn];
void dfs(int x)
{
    s[x] = 1LL;
    for (int i:adj[x])
    {
        dfs(i);
        s[x]=s[x]*s[i]%mod;
    }
    s[x] = s[x]*(ll)adj[x].size()%mod;
}
void dfs2(int x, ll val)
{
    if (x>=n)
    {
        dp[x-n+1] = val;
        return;
    }
    vector <ll> pre,suf;
    for (int i:adj[x])
    {
        pre.push_back(s[i]);
        suf.push_back(s[i]);
    }
    for (int i=1; i<pre.size(); i++) pre[i]=pre[i]*pre[i-1]%mod;
    for (int i=suf.size()-2; i>=0; i--) suf[i]=suf[i]*suf[i+1]%mod;
    int cnt=0;
    for (int i:adj[x])
    {
        ll val2 = val;
        if (cnt>0) val2=val2*pre[cnt-1]%mod;
        if (cnt<suf.size()-1) val2=val2*suf[cnt+1]%mod;
        dfs2(i,val2);
    }

}
ll f[4*maxn]; bool rev[4*maxn];
void pushrev(int x, int lx, int rx)
{
    f[x] = (sdp[rx]-sdp[lx-1]+mod-f[x]+mod)%mod;
    rev[x]^=1;
}
void down(int x, int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (rev[x])
    {
        pushrev(2*x,lx,mid);
        pushrev(2*x+1,mid+1,rx);
        rev[x]=0;
    }
}
void add(int x, int lx, int rx, int l, int r)
{
    if (lx>r||rx<l) return;
    if (lx>=l&&rx<=r)
    {
        pushrev(x,lx,rx);
        return;
    }
    int mid=(lx+rx)/2;
    down(x,lx,rx);
    add(2*x,lx,mid,l,r);
    add(2*x+1,mid+1,rx,l,r);
    f[x]=(f[2*x]+f[2*x+1])%mod;
}
void build(int x, int lx, int rx)
{
    rev[x]=0;
    if (lx==rx)
    {
        f[x]=0LL;
        if (a[x]) f[x] = dp[x];
        return;
    }
    int mid=(lx+rx)/2;
    build(2*x,lx,mid); build(2*x+1,mid+1,rx);
    f[x]=(f[2*x]+f[2*x+1])%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n=N; m=M;
    for (int i=0; i<n+m; i++) adj[i].clear();
    for (int i=1; i<n+m; i++)
    {
        int u=i; int v=P[i];
        adj[v].push_back(u);
    }

    for (int i=n; i<n+m; i++) a[i-n+1]=A[i-n];
    dfs(1); dfs2(1,1LL);
    sdp[0]=0LL;
    for (int i=1; i<=m; i++) sdp[i]=(dp[i]+sdp[i-1])%mod;
    build(1,1,m);
}

int count_ways(int L, int R) {
    L++; R++;
    add(1,1,m,L,R);
    int ans = (f[1])%mod;
    return ans;
}

Compilation message

circuit.cpp: In function 'void dfs2(int, long long int)':
circuit.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=1; i<pre.size(); i++) pre[i]=pre[i]*pre[i-1]%mod;
      |                   ~^~~~~~~~~~~
circuit.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (cnt<suf.size()-1) val2=val2*suf[cnt+1]%mod;
      |             ~~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 689 ms 8180 KB 1st lines differ - on the 1st token, expected: '431985922', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 689 ms 8180 KB 1st lines differ - on the 1st token, expected: '431985922', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -