oj.uz

Submission #90990

# Submission time Handle Problem Language Result Execution time Memory
90990 2018-12-25T12:29:55 Z Milki CSS (COI14_css) C++14
60 / 100
 1313 ms 81308 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 = 17;
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 s){
    int ret = s[0];
    FOR(i, 1, sz(s))
      ret = add(mul(ret, baza), s[i]);
    klasa.insert(ret);
  }
  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 s){
    int ret = s[0];
    FOR(i, 1, sz(s))
      ret = add(mul(ret, baza), s[i]);
    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){
    for(auto it : v[pos].hesh){
      if(!element[x].check(it))
        return dp[x][pos][tip] = 0;
    }
    //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);

    return dp[x][pos][tip] = ( ret | (sz(v) == 1) );
  }

  if(tip == 0){
    ret = 1;
    for(auto it : v[pos].hesh)
      ret &= element[x].check(it);

    int novi = 0;
    for(auto e : E[x])
      novi |= dfs(e, pos, tip);
    if(ret == 0)
      return dp[x][pos][tip] = novi;

    for(auto e : E[x])
      novi |= dfs(e, pos - 1, v[pos].tip);
    return dp[x][pos][tip] = (novi | (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 | (pos == 0));
  }

  assert(n == 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 ++;
    }
    x.ubaci(name);
    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 << 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 888 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 22912 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 37520 KB Output is correct
2 Correct 666 ms 61496 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 61496 KB Output is correct
2 Correct 615 ms 61544 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 61544 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 61544 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 171 ms 61544 KB Output is correct
2 Correct 1313 ms 81308 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 81308 KB Output is correct
2 Correct 652 ms 81308 KB Output is correct