oj.uz

Submission #52313

# Submission time Handle Problem Language Result Execution time Memory
52313 2018-06-25T09:34:31 Z Milki Dijamant (COI16_dijament) C++14
100 / 100
 339 ms 16372 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = 0; i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

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

const int MAXN = 1e3 + 5;

int n;
map<string, int> id;
vector <int> parents[MAXN];
bool bio[MAXN];
int curr;

bool check(string &name, vector <string> &par){
    if(id[name] != 0) return false;
    for(auto it : par){
        if(id[it] == 0)
            return false;
    }
    vector <int> parId;
    REP(i, (int)par.size()){
        parId.push_back(id[par[i]]);
    }
    sort(parId.rbegin(), parId.rend());

    memset(bio, 0, curr + 1);
    for(auto it : parId){
        if(bio[it]) continue;

        for(auto p : parents[it]){
            if(bio[p]) return false;
            bio[p] = 1;
        }
    }

    id[name] = ++curr;
    for(auto it : parId)
        bio[it] = 1;

    FOR(i, 1, curr)
        if(bio[i])
            parents[curr].push_back(i);
    return true;
}

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

    cin >> n;
    REP(i, n){
        string name, tmp;
        vector<string> v;
        cin >> name >> tmp;
        cin >> tmp;
        while(tmp != ";"){
            v.push_back(tmp);
            cin >> tmp;
        }

        if(check(name, v))
            cout << "ok\n";
        else
            cout << "greska\n";
    }
}

Subtask #1
13.0 / 13.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 4 ms 568 KB Output is correct
7 Correct 3 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 648 KB Output is correct
10 Correct 2 ms 648 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 4 ms 568 KB Output is correct
7 Correct 3 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 648 KB Output is correct
10 Correct 2 ms 648 KB Output is correct
11 Correct 2 ms 648 KB Output is correct
12 Correct 2 ms 780 KB Output is correct
13 Correct 2 ms 780 KB Output is correct
14 Correct 3 ms 780 KB Output is correct
15 Correct 3 ms 780 KB Output is correct
16 Correct 3 ms 888 KB Output is correct
17 Correct 2 ms 888 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 4 ms 900 KB Output is correct
20 Correct 2 ms 900 KB Output is correct
21 Correct 3 ms 932 KB Output is correct
22 Correct 2 ms 944 KB Output is correct
23 Correct 3 ms 948 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 3428 KB Output is correct
2 Correct 339 ms 7868 KB Output is correct
3 Correct 74 ms 9588 KB Output is correct
4 Correct 4 ms 9588 KB Output is correct
5 Correct 6 ms 9588 KB Output is correct
6 Correct 9 ms 9588 KB Output is correct
7 Correct 20 ms 9668 KB Output is correct
8 Correct 31 ms 10108 KB Output is correct
9 Correct 35 ms 10596 KB Output is correct
10 Correct 9 ms 10596 KB Output is correct
11 Correct 8 ms 10660 KB Output is correct
12 Correct 289 ms 16372 KB Output is correct