oj.uz

Submission #91134

# Submission time Handle Problem Language Result Execution time Memory
91134 2018-12-26T10:47:52 Z Milki CSS (COI14_css) C++14
60 / 100
 1161 ms 85736 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7, baza = 1307;
const int MAXN = 5e3 + 5;

int add(int x, int y) {
  x += y;
  if(x >= mod) return x - mod;
  return x;
}

int mul(int x, int y) {
  return (ll) x * y % mod;
}

int sub(int x, int y) {
  x -= y;
  if(x < 0) return x + mod;
  return x;
}

struct elementi{
  string name = "";
  set <int> klasa;
  int id = -1;

  void ubaci(string ses){
    int ret = ses[0];
    FOR(i, 1, sz(ses))
      ret = add(mul(ret, baza), ses[i]);
    klasa.insert(ret);
    //cout << "RETOOOOO " _ ret << "\n";
  }
  bool check(int x){
    return klasa.find(x) != klasa.end();
  }
};

int n, m;
string s;
elementi element[MAXN];
vector <int> E[MAXN];

void parse1(){
  vector <int> v;
  stack <int> stek;

  cin >> n;
  cin.get();

  int curr = 0;
  REP(i, n){

    s = ""; getline(cin, s);
    if(s[1] == '/'){
      stek.pop(); continue;
    }
    if(sz(stek)) { E[curr].pb(stek.top()); }
    stek.push(curr);
    int start = 9;
    string name = ""; while((int)s[start] != 39) { name += s[start]; start ++; }
    start += 9;
    element[curr].name = name;
    element[curr].id = curr;

    string kek = "";
    while( (int)s[start] != 39){
      if(s[start] != ' ')
        kek += s[start];
      else{
        element[curr].ubaci(kek);
        kek = "";
      }
      start ++;
    }
    if(kek != ""){
      element[curr].ubaci(kek);
    }
    curr ++;
  }
}

struct event{
  int tip = 0, id;
  vector <int> hesh;
  void ubaci(string ses){
    int ret = ses[0];
    FOR(i, 1, sz(ses))
      ret = add(mul(ret, baza), ses[i]);
    //cout << "RETETE " _ ses << "\n";
    hesh.pb(ret);
  }
  void reset(){
    tip = id = 0;
    hesh.clear();
  }
};

vector <string> sol;
vector <event> v;
int dp[MAXN][MAXN][2];

int dfs(int x, int pos, int tip){
  if(pos < 0) return 1;
  if(dp[x][pos][tip] != -1) return dp[x][pos][tip];
  int ret = 0;

  if(pos == sz(v) - 1){
    ret = 1;
    for(auto it : v[pos].hesh){
      //cout << it << " it\n";
      ret &= element[x].check(it);
    }
    //cout << sz(element[x].klasa) << " sz\n";
    if(ret == 0)
      return dp[x][pos][tip] = ret;
    //cout << "iks" _ x _ pos << "\n";
    //cout << "iks" _ x << "\n";
    //cout << x << " x je ovo\n";
    //cout << element[x].name << "\n";
    ret = 0;
    for(auto e : E[x]){
      ret |= dfs(e, pos - 1, v[pos].tip);
    }
    //cout << ret << " iks" _ x << "\n";
    return dp[x][pos][tip] = ( ret | (int)(pos == 0) );
  }

  if(tip == 0){
    ret = 1;
    for(auto it : v[pos].hesh)
      ret &= element[x].check(it);
    if(ret == 0){
      for(auto e : E[x])
        ret |= dfs(e, pos, tip);
      return dp[x][pos][tip] = ret;
    }
    else{
      ret = 0;
      for(auto e : E[x]){
        ret |= dfs(e, pos, tip);
        ret |= dfs(e, pos - 1, v[pos].tip);
      }
      return dp[x][pos][tip] = (ret | (pos == 0));
    }
  }
  else{
    ret = 1;
    for(auto it : v[pos].hesh)
      ret &= element[x].check(it);
    if(ret == 0)
      return dp[x][pos][tip] = ret;

    ret = 0;
    for(auto e : E[x])
      ret |= dfs(e, pos - 1, v[pos].tip);
    return dp[x][pos][tip] = (ret | (int)(pos == 0));
  }
}

void parse2(){
  cin >> m;
  cin.get();

  REP(testcase, m){
    s = ""; getline(cin, s);
    event x;

    string name = "";
    int start = 0;
    while(start < sz(s)){

      if(s[start] >= 'a' && s[start] <= 'z'){
        name += s[start];
      }
      else if(s[start] == '.'){
        if(name != "") { x.ubaci(name); name = ""; }
      }
      else if(s[start] == ' '){
        if(x.id != -1) { x.ubaci(name);  name = ""; v.pb(x); x.reset();}
      }
      else if(s[start] == '>'){
        x.tip = 1; start ++;
      }
      start ++;
    }
    if(name != "")
      x.ubaci(name);
    if(sz(x.hesh))
      v.pb(x);

    int N = n / 2;
    REP(i, N)
      REP(j, sz(v) + 1)
        dp[i][j][0] = dp[i][j][1] = -1;

    REP(i, N){
      if(dp[i][sz(v) - 1][0] == -1){
        dfs(i, sz(v) - 1, 0);
      }
      if(dp[i][sz(v) - 1][0] == 1)
        sol.pb(element[i].name);
    }
    //cout << "DPDPDPDP " _ dp[0][0][0] << "\n";
    cout << sz(sol);
    for(auto it : sol)
      cout << " " << it;
    cout << "\n";

    v.clear(); sol.clear();
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  parse1(); parse2();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1016 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23216 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 23216 KB Output isn't correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 41512 KB Output is correct
2 Correct 639 ms 65804 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 65804 KB Output is correct
2 Correct 682 ms 66004 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 66004 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 66004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 66004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 66004 KB Output is correct
2 Correct 1161 ms 85736 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 85736 KB Output is correct
2 Correct 595 ms 85736 KB Output is correct