Submission #910896

#TimeUsernameProblemLanguageResultExecution timeMemory
910896tnunDigital Circuit (IOI22_circuit)C++17
0 / 100
22 ms19092 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back int N,M; vector<int> P; vector<int> A; ll int mod=1000002022; vector<int> adj[200050]; ll int one[200050]={0}; ll int zer[200050]={0}; void dfs(){ for(int node=N+M-1;node>=0;node--){ if(node>=N){ if(A[node-N]==1){ one[node]=1; zer[node]=0; }else{ one[node]=0; zer[node]=1; } continue; } ll int all=1; for(int i=0;i<adj[node].size();i++){ all*=(one[adj[node][i]]+zer[adj[node][i]]); all=all%mod; } for(int i=0;i<adj[node].size();i++){ one[node]+=(one[adj[node][i]])*all/(one[adj[node][i]]+zer[adj[node][i]]); one[node]=one[node]%mod; } all=all*adj[node].size(); all=all%mod; zer[node]=all-one[node]; } } int count_ways(int l,int r){ memset(one, 0, sizeof(one)); memset(zer, 0, sizeof(zer)); for(int i=l;i<=r;i++){ A[i-N]=(A[i-N]+1)%2; } // for(int i=0;i<A.size();i++){ // cout<<A[i]<<" "; // } // cout<<endl; dfs(); // for(int i=0;i<N+M;i++){ // cout<<i<<" "<<one[i]<<" "<<zer[i]<<endl; // } return one[0]; } void init(int N,int M, vector<int> P,vector<int> A){ for(int i=1;i<N+M;i++){ adj[P[i]].pb(i); } } /*int main(){ cin>>N>>M; for(int i=0;i<N+M;i++){ int k; cin>>k; P.pb(k); } for(int i=0;i<M;i++){ int k; cin>>k; A.pb(k); } init(N,M,P,A); int Q; cin>>Q; for(int i=0;i<Q;i++){ int x,c; cin>>x>>c; cout<<count_ways(x,c)<<endl; } }*/

Compilation message (stderr)

circuit.cpp: In function 'void dfs()':
circuit.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<adj[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~
circuit.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0;i<adj[node].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...