Submission #839177

#TimeUsernameProblemLanguageResultExecution timeMemory
839177dolphingarlicHomework (CEOI22_homework)C++17
100 / 100
290 ms177580 KiB
#include <bits/stdc++.h> using namespace std;const int N=3e6;vector<int>g[N];int p[N],n=0,t[N],sz[N],mn[N],mx[N];void dfs(int z=1){if(!g[z].size())return;int u=g[z][0],v=g[z][1];dfs(u);dfs(v);sz[z]+=sz[u]+sz[v];if(t[z]==1){mn[z]=min(mn[u],mn[v]);mx[z]=mx[u]+mx[v]-1;}if(t[z]==2){mn[z]=mn[u]+mn[v];mx[z]=max(sz[u]+mx[v],sz[v]+mx[u]);}}main(){string s;cin>>s;int c=0;for(int i=0;i<s.size();i++){if(s[i]=='m'){p[++n]=c;g[c].push_back(n);c=n;if(s[i+2]=='n')t[c]=1;else t[c]=2;i+=3;}else if(s[i]=='?'){p[++n]=c;g[c].push_back(n);c=n;mn[c]=mx[c]=sz[c]=1;}else c=p[c];}dfs();cout<<mx[1]-mn[1]+1;}

Compilation message (stderr)

Main.cpp:2:310: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    2 | using namespace std;const int N=3e6;vector<int>g[N];int p[N],n=0,t[N],sz[N],mn[N],mx[N];void dfs(int z=1){if(!g[z].size())return;int u=g[z][0],v=g[z][1];dfs(u);dfs(v);sz[z]+=sz[u]+sz[v];if(t[z]==1){mn[z]=min(mn[u],mn[v]);mx[z]=mx[u]+mx[v]-1;}if(t[z]==2){mn[z]=mn[u]+mn[v];mx[z]=max(sz[u]+mx[v],sz[v]+mx[u]);}}main(){string s;cin>>s;int c=0;for(int i=0;i<s.size();i++){if(s[i]=='m'){p[++n]=c;g[c].push_back(n);c=n;if(s[i+2]=='n')t[c]=1;else t[c]=2;i+=3;}else if(s[i]=='?'){p[++n]=c;g[c].push_back(n);c=n;mn[c]=mx[c]=sz[c]=1;}else c=p[c];}dfs();cout<<mx[1]-mn[1]+1;}
      |                                                                                                                                                                                                                                                                                                                      ^~~~
Main.cpp: In function 'int main()':
Main.cpp:2:354: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | using namespace std;const int N=3e6;vector<int>g[N];int p[N],n=0,t[N],sz[N],mn[N],mx[N];void dfs(int z=1){if(!g[z].size())return;int u=g[z][0],v=g[z][1];dfs(u);dfs(v);sz[z]+=sz[u]+sz[v];if(t[z]==1){mn[z]=min(mn[u],mn[v]);mx[z]=mx[u]+mx[v]-1;}if(t[z]==2){mn[z]=mn[u]+mn[v];mx[z]=max(sz[u]+mx[v],sz[v]+mx[u]);}}main(){string s;cin>>s;int c=0;for(int i=0;i<s.size();i++){if(s[i]=='m'){p[++n]=c;g[c].push_back(n);c=n;if(s[i+2]=='n')t[c]=1;else t[c]=2;i+=3;}else if(s[i]=='?'){p[++n]=c;g[c].push_back(n);c=n;mn[c]=mx[c]=sz[c]=1;}else c=p[c];}dfs();cout<<mx[1]-mn[1]+1;}
      |                                                                                                                                                                                                                                                                                                                                                                 ~^~~~~~~~~
#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...