Submission #739520

#TimeUsernameProblemLanguageResultExecution timeMemory
739520TrunktyDigital Circuit (IOI22_circuit)C++17
100 / 100
1286 ms57560 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; //#define int ll #include "circuit.h" ll n,m,mod=1000002022; vector<ll> roads[200005]; ll comb[200005],val[200005],pref[200005],suff[200005]; map<ll,ll> todfs[200005]; ll sumi[800005],segtree[800005]; ll lazy[800005]; void build(ll node, ll l, ll r){ if(l==r){ sumi[node] = val[l]; } else{ ll mid = (l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); sumi[node] = sumi[node*2]+sumi[node*2+1]; sumi[node] %= mod; } } void pushdown(ll node, ll l, ll r){ if(lazy[node]){ segtree[node] = sumi[node]-segtree[node]; segtree[node] += mod; segtree[node] %= mod; if(l!=r){ lazy[node*2] ^= 1; lazy[node*2+1] ^= 1; } lazy[node] = 0; } } void update(ll node, ll l, ll r, ll needl, ll needr){ pushdown(node,l,r); if(l>needr or r<needl){ return; } else if(l>=needl and r<=needr){ lazy[node] ^= 1; pushdown(node,l,r); } else{ ll mid = (l+r)/2; update(node*2,l,mid,needl,needr); update(node*2+1,mid+1,r,needl,needr); pushdown(node*2,l,mid); pushdown(node*2+1,mid+1,r); segtree[node] = segtree[node*2]+segtree[node*2+1]; segtree[node] %= mod; } } void dfs1(ll x){ comb[x] = 1; if(x>=n){ return; } for(ll i:roads[x]){ dfs1(i); comb[x] *= comb[i]; comb[x] %= mod; } comb[x] *= roads[x].size(); comb[x] %= mod; } void dfs2(ll x, ll c){ if(x>=n){ val[x] = c; return; } pref[0] = 1; for(ll i=1;i<=roads[x].size();i++){ pref[i] = comb[roads[x][i-1]]*pref[i-1]; pref[i] %= mod; } suff[roads[x].size()+1] = 1; for(ll i=roads[x].size();i>=1;i--){ suff[i] = comb[roads[x][i-1]]*suff[i+1]; suff[i] %= mod; } for(ll i=1;i<=roads[x].size();i++){ todfs[x][roads[x][i-1]] = (((pref[i-1]*suff[i+1])%mod)*c)%mod; } for(ll i:roads[x]){ dfs2(i,todfs[x][i]); } } void init(int N, int M, vector<int> p, vector<int> a){ n = N; m = M; for(ll i=1;i<=n+m-1;i++){ roads[p[i]].push_back(i); } dfs1(0); dfs2(0,1); build(1,0,n+m-1); for(ll i=0;i<a.size();i++){ if(a[i]){ update(1,0,n+m-1,i+n,i+n); } } } int count_ways(int l, int r){ update(1,0,n+m-1,l,r); return segtree[1]; }

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(ll, ll)':
circuit.cpp:81:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(ll i=1;i<=roads[x].size();i++){
      |                ~^~~~~~~~~~~~~~~~~
circuit.cpp:90:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll i=1;i<=roads[x].size();i++){
      |                ~^~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:107:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(ll i=0;i<a.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...