제출 #632122

#제출 시각아이디문제언어결과실행 시간메모리
632122drkarlicio2107Homework (CEOI22_homework)C++14
23 / 100
1092 ms524288 KiB
#include <bits/stdc++.h> using namespace std; int ind=0; int t [2000010]; vector <int> g [2000010]; int n=0; int maxi=0; void rec (string s, int i, int par){ maxi=max (maxi, i); //cout << i << endl; if (s [i]=='?'){ t [ind]=2; g [par].push_back (ind); ind++; n++; } if (s [i+1]=='i'){ t [ind]=0; g [par].push_back (ind); ind++; rec (s, i+4, ind-1); } if (s [i+1]=='a'){ t [ind]=1; g [par].push_back (ind); ind++; rec (s, i+4, ind-1); } if (i==0) return ; i=maxi; //cout << maxi << endl; while (s [i]!=',') i++; i++; //cout << i << " " << ind << endl; maxi=max (maxi, i); if (s [i]=='?'){ t [ind]=2; g [par].push_back (ind); ind++; n++; } if (s [i+1]=='i'){ t [ind]=0; g [par].push_back (ind); ind++; rec (s, i+4, ind-1); } if (s [i+1]=='a'){ t [ind]=1; g [par].push_back (ind); ind++; rec (s, i+4, ind-1); } return ; } pair <int, int> sol (int x){ if (t [x]==2) return {1, n}; int l1=sol (g[x][0]).first; int l2=sol (g[x][1]).first; int r1=sol (g[x][0]).second; int r2=sol (g[x][1]).second; if (t [x]==1) return {l1+l2, max (r1, r2)}; return {min (l1, l2), r1+r2-n-1}; } int main(){ string s; cin >> s; rec (s, 0, 2000001); //cout << g [0].size(); cout << sol (0).second-sol (0).first+1; return 0; }
#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...