oj.uz

Submission #105491

# Submission time Handle Problem Language Result Execution time Memory
105491 2019-04-12T16:39:44 Z JakubLap Palinilap (COI16_palinilap) C++14
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1024;

map<long long, int> ID;
bitset<N> a[N];

int n;

long long getCode(string s) {
    long long ans = 0;
    for (int i = 0; i < s.size(); ++i)
        ans = ans * 26 + (s[i] - 'a');
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int nQuery; cin >> nQuery;
    while (nQuery--) {
        string u; cin >> u;
        long long u_code = getCode(u);
        char colon; cin >> colon;
        string v;
        vector<int> adj;
        bool fail = ID.count(u_code);
        while (cin >> v) {
            if (v == ";") break;
            long long code = getCode(v);
            if (!ID.count(code)) {
                fail = true;
            } else {
                adj.push_back(ID[code]);
            }
        }
        if (fail) {
            cout << "greska\n";
            continue;
        }
        sort(adj.begin(), adj.end(), greater<int>());
        bitset<N> was;
        for (int i = 0; i < adj.size(); ++i) {
            int v = adj[i];
            bool isRoot = true;
            for (int j = 0; j < i; ++j) if (a[adj[j]].test(v)) {
                isRoot = false;
                break;
            }
            if (isRoot) {
                if ((was & a[v]).any()) {
                    fail = true;
                    break;
                }
                was |= a[v];
            }
        }
        if (fail) {
            cout << "greska\n";
            continue;
        }
        cout << "ok\n";
        ID[u_code] = ++n;
        for (int v : adj) {
            a[n] |= a[v];
            a[n].set(v);
        }
    }
    return 0;
}

Compilation message

palinilap.cpp: In function 'long long int getCode(std::__cxx11::string)':
palinilap.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i)
                     ~~^~~~~~~~~~
palinilap.cpp: In function 'int main()':
palinilap.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj.size(); ++i) {
                         ~~^~~~~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 37.0

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

Subtask #3
0 / 46.0

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