제출 #1085307

#제출 시각아이디문제언어결과실행 시간메모리
1085307underwaterkillerwhale디지털 회로 (IOI22_circuit)C++17
0 / 100
8 ms2136 KiB
//#include "circuit.h" #include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define iter(id, v) for(auto id : v) #define fs first #define se second #define MP make_pair #define pb push_back #define bit(msk, i) ((msk >> i) & 1) #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 2e3 + 7; const int Mod = 1e9 + 2022; const int INF = 1e9; const ll BASE = 137; const int szBL = 350; int n, m, Q; int P[N], a[N]; vector<int> ke[N]; pii qr[N]; bool ok4 = 0; namespace sub3 { ll dp[N][2], f[N][N]; void dfs (int u, int p) { iter (&v, ke[u]) { if (v != p) {///aware!!!!!!!! dfs(v, u); } } int m = SZ(ke[u]); rep (i, 0, m) rep (j, 0, m) f[i][j] = 0; f[0][0] = 1; rep (i, 1, m) { int v = ke[u][i - 1]; rep (j, 0, m ) { f[i][j] = f[i - 1][j] * dp[v][0] % Mod; if (j) (f[i][j] += f[i - 1][j - 1] * dp[v][1] % Mod) %= Mod; // cout << u<<" "<<v<<","<<i<<" "<<j<<" "<<f[i][j] <<"\n"; } } ll pre = f[m][0]; rep (i, 1, m) { (dp[u][0] += pre) %= Mod; (pre += f[m][i]) %= Mod; } ll suf = 0; reb (i, m, 1) { (suf += f[m][i]) %= Mod; (dp[u][1] += suf) %= Mod; } // cout << u<<" "<<dp[u][0]<<","<<dp[u][1] <<"\n"; } ll solution() { rep (i, 1, n + m) rep (j, 0, 1) dp[i][j] = 0; rep (i, n + 1, n + m) dp[i][a[i]] = 1; dfs(1, 0); return dp[1][1]; // cout << dp[1][1] <<"\n"; } } namespace sub4 { const ll N2 = 1e5 + 7; ll dp[N2][2]; int pa[N2]; bool check () { int K = 1; while (K < m) K *= 2; if (K == m && m == n + 1) { rep (i, 1, n + m - 1) if (P[i + 1] != (i - 1) / 2) return 0; return 1; } return 0; } void update (int u) { if (SZ(ke[u]) == 0) { dp[u][a[u]] = 1; dp[u][a[u] ^ 1] = 0; return; } int v1 = ke[u][0], v2 = ke[u][1]; ll delta = (dp[v1][0] * dp[v2][1] % Mod + dp[v1][1] * dp[v2][0] % Mod) % Mod; dp[u][0] = (delta + 2LL * dp[v1][0] * dp[v2][0] % Mod) % Mod; dp[u][1] = (delta + 2LL * dp[v1][1] * dp[v2][1] % Mod) % Mod; } void dfs (int u, int p) { pa[u] = p; iter (&v, ke[u]) { dfs(v, u); } update (u); } void init () { dfs(1, 0); } ll solution(int u) { while (u != 0) { update(u); u = pa[u]; } return dp[1][1]; } } int count_ways (int L, int R) { ++L; ++R; rep (i, L, R) a[i] ^= 1; if (L == R && ok4) return sub4 :: solution(L); else return sub3 :: solution(); } void init (int _n, int _m, vector<int> _P, vector<int> _a) { n = _n; m = _m; rep (i, 1, n + m) P[i] = _P[i - 1]; rep (i, 1, m) a[i + n] = _a[i - 1]; rep (i, 1, n + m) { if (i > 1) { ke[P[i] + 1].pb(i); // cout << i <<" "<<P[i] + 1 <<"\n"; } } ok4 = sub4 :: check(); if (ok4) sub4 :: init(); } void solution() { cin >> n >> m >> Q; rep (i, 1, n + m) { cin >> P[i]; if (i > 1) { ke[P[i] + 1].pb(i); // cout << i <<" "<<P[i] + 1 <<"\n"; } } rep (i, n + 1, n + m) cin >> a[i]; if (sub4 :: check()) sub4 :: init(); rep (i, 1, Q) { int L, R; cin >> L >> R; cout << count_ways(L, R) <<"\n"; } } //#define file(name) freopen(name".inp","r",stdin); \ //freopen(name".out","w",stdout); //int main () { //// file("c"); // ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); // int num_Test = 1; //// init(3, 4, {-1, 0, 1, 2, 1, 1, 0}, {1, 0, 1, 0}); //// cout << count_ways(3, 4) <<"\n"; //// cin >> num_Test; // while (num_Test--) // solution(); //} /* no bug +5 3 4 3 -1 0 0 1 1 2 2 1 0 1 0 3 3 4 4 2 2 */

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp:170:1: warning: multi-line comment [-Wcomment]
  170 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
#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...