Submission #724423

#	Time	Username	Problem	Language	Result	Execution time	Memory
724423		cig32	Homework (CEOI22_homework)	C++17	100 / 100	391 ms	210852 KiB

Main

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e6 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
string s;
vector<int> adj[MAXN];
char tag[MAXN];
int n;
int ma[MAXN], mi[MAXN];
int sz[MAXN];
void dfs(int node) {
  sz[node] = (node < n);
  for(int x: adj[node]) {
    dfs(x);
    sz[node] += sz[x];
  }
}
void dpf(int node) {
  if(adj[node].empty()) {
    ma[node] = mi[node] = 1;
    return;
  }
  for(int x: adj[node]) dpf(x);
  if(tag[node] == 'a') {
    for(int x: adj[node]) ma[node] = max(ma[node], sz[node] - (sz[x] - ma[x]));
    for(int x: adj[node]) mi[node] += mi[x];
  }
  else {
    for(int x: adj[node]) ma[node] += ma[x] - 1;
    ma[node] += 1;
    mi[node] = 1e9;
    for(int x: adj[node]) mi[node] = min(mi[node], mi[x]);
  }
}
void solve(int tc) {
  cin >> s;
  n = 0;
  for(char c: s) n += (c == '?');
  vector<int> t;
  int o = 0;
  for(char c: s) {
    if(c == '?') t.push_back(o++);
    else if(c == '(') t.push_back(-1);
    else if(c == ')') t.push_back(-2);
    else if(c == ',') t.push_back(-3);
    else if(c == 'm') t.push_back(-4);
    else if(c == 'a') t.push_back(-5);
    else if(c == 'x') t.push_back(-6);
    else if(c == 'i') t.push_back(-7);
    else t.push_back(-8);
  }
  vector<int> wow;
  for(int i=0; i<t.size(); i++) {
    if(t[i] != -2) wow.push_back(t[i]);
    else {
      //max(?,?)
      //       ^ i
      //^ i-7
      int len = wow.size();
      int ch1 = wow[len-1];
      int ch2 = wow[len-3];
      int cur = o++;
      adj[cur].push_back(ch1);
      adj[cur].push_back(ch2);
      //cout << cur << " " << ch1 << "\n";
      //cout << cur << " " << ch2 << "\n";
      tag[cur] = (wow[len-5] == -6 ? 'a' : 'i');
      for(int j=len-1; j>=len-7; j--) wow.pop_back();
      wow.push_back(cur);
    }
  }
  int rt = o - 1;
  dfs(rt);
  dpf(rt);
  cout << ma[rt] - mi[rt] + 1 << "\n";
  //for(int i=0; i<=rt; i++) cout << "[" << mi[i] << ", " << ma[i] << "]\n";
} 
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

/*

*/

Compilation message (stderr)

Main.cpp: In function 'void solve(int)':
Main.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i=0; i<t.size(); i++) {
      |                ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34