oj.uz

Submission #20991

# Submission time Handle Problem Language Result Execution time Memory
20991 2017-03-27T09:31:45 Z model_code Dijamant (COI16_dijament) C++11
100 / 100
 503 ms 5196 KB 
// Autor: Ante Derek

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <cassert>
#include <algorithm>

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " << 

using namespace std;

map<string, int> index;
vector<vector<int>> parents;

int process(const string &k, const vector<string> &p) {
  int m = index.size();
  if (index.count(k))
    return 0;
  vector<int> pp;
  for (auto x : p) {
    if (index.count(x) == 0)
      return 0;
    pp.push_back(index[x]);
  }
  sort(pp.begin(), pp.end());
  vector<int> seen(m, 0);
  for (int i=(int)pp.size()-1; i>=0; i--) {
    int y = pp[i];
    if (seen[y])
      continue ;
    for (auto z : parents[y]) {
      if (seen[z])
        return 0;
      seen[z] = 1;
    }
  }
  index[k] = m;
  for (auto y : pp)
    seen[y] = 1;
  parents.push_back(vector<int>());
  for (int i=0; i<m; i++)
    if (seen[i])
      parents[m].push_back(i);
  return 1;
}

int main() {
  int n;
  cin >> n;
  for (int i=0; i<n; i++) {
    string k;
    vector<string> p;
    string temp;
    cin >> k >> temp;
    assert(temp == ":");
    cin >> temp;
    while (temp != ";") {
      p.push_back(temp);
      cin >> temp;
    }
    if (process(k, p))
      cout << "ok" << endl;
    else
      cout << "greska" << endl;
  }
  return 0;
}

Compilation message

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct
5 Correct 0 ms 2028 KB Output is correct
6 Correct 3 ms 2160 KB Output is correct
7 Correct 3 ms 2028 KB Output is correct
8 Correct 0 ms 2028 KB Output is correct
9 Correct 0 ms 2028 KB Output is correct
10 Correct 0 ms 2028 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct
5 Correct 0 ms 2028 KB Output is correct
6 Correct 3 ms 2160 KB Output is correct
7 Correct 3 ms 2028 KB Output is correct
8 Correct 0 ms 2028 KB Output is correct
9 Correct 0 ms 2028 KB Output is correct
10 Correct 0 ms 2028 KB Output is correct
11 Correct 0 ms 2028 KB Output is correct
12 Correct 0 ms 2028 KB Output is correct
13 Correct 0 ms 2028 KB Output is correct
14 Correct 0 ms 2028 KB Output is correct
15 Correct 3 ms 2028 KB Output is correct
16 Correct 0 ms 2028 KB Output is correct
17 Correct 0 ms 2028 KB Output is correct
18 Correct 0 ms 2028 KB Output is correct
19 Correct 0 ms 2028 KB Output is correct
20 Correct 0 ms 2028 KB Output is correct
21 Correct 0 ms 2028 KB Output is correct
22 Correct 0 ms 2028 KB Output is correct
23 Correct 0 ms 2028 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 4972 KB Output is correct
2 Correct 503 ms 5196 KB Output is correct
3 Correct 246 ms 2180 KB Output is correct
4 Correct 3 ms 2160 KB Output is correct
5 Correct 6 ms 2160 KB Output is correct
6 Correct 19 ms 2164 KB Output is correct
7 Correct 43 ms 2164 KB Output is correct
8 Correct 39 ms 2160 KB Output is correct
9 Correct 49 ms 2160 KB Output is correct
10 Correct 19 ms 2160 KB Output is correct
11 Correct 3 ms 2160 KB Output is correct
12 Correct 463 ms 4832 KB Output is correct