Submission #1070149

#TimeUsernameProblemLanguageResultExecution timeMemory
1070149UnforgettableplDigital Circuit (IOI22_circuit)C++17
18 / 100
3043 ms2904 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; const long long modulo = 1e9+2022; namespace { int N,M; vector<vector<int>> adj; vector<int> A; } void init(int N,int M,vector<int> P,vector<int> A){ ::N = N; ::M = M; ::A = move(A); adj = vector<vector<int>>(N); for(int i=1;i<N+M;i++)adj[P[i]].emplace_back(i); } int count_ways(int L,int R){ for(int i=L;i<=R;i++)A[i-N]^=1; function<pair<long long,long long>(int)> dfs = [&](int x)->pair<long long,long long>{ if(x>=N) { return {A[x-N],1}; } long long tot_ways = adj[x].size(); vector<long long> DP(adj[x].size()+1); DP[0]=1; for(int&i:adj[x]) { auto temp = dfs(i); tot_ways*=temp.second; tot_ways%=modulo; long long bad_ways = (temp.second-temp.first+modulo)%modulo; for(int j=adj[x].size();j>=0;j--) { DP[j]*=bad_ways; DP[j]%=modulo; if(j)DP[j]+=temp.first*DP[j-1]; DP[j]%=modulo; } } long long ans = 0; for(long long i=1;i<=adj[x].size();i++) { ans+=DP[i]*i; ans%=modulo; } return {ans,tot_ways}; }; return dfs(0).first; }

Compilation message (stderr)

circuit.cpp: In lambda function:
circuit.cpp:43:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(long long i=1;i<=adj[x].size();i++) {
      |                           ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...