Submission #990708

#	Time	Username	Problem	Language	Result	Execution time	Memory
990708		vjudge1	Dijamant (COI16_dijament)	C++17	100 / 100	570 ms	5712 KiB

dijament

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n;
bool derived[N][N], sibling[N][N];
map<string, int> mp;

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

    cin >> n;
    for (int ii = 0; ii < n; ii ++){
        string inp;
        cin >> inp;
        
        vector<string> vecs;
        while (inp != ";"){
            if (inp != ":")
                vecs.push_back(inp);
            cin >> inp;
        }

        bool good = 1;
        if (mp.find(vecs[0]) != mp.end()){
            // cout << vecs[0] << " was already there" << endl;
            good = 0;
        }
        for (int i = 1; i < vecs.size(); i ++){
            if (mp.find(vecs[i]) == mp.end()){
                // cout << vecs[i] << " was not found" << endl;
                good = 0;
            }
        }

        if (!good){
            cout << "greska" << endl;
            continue;
        }

        vector<int> vec;
        for (int i = 1; i < vecs.size(); i ++)
            vec.push_back(mp[vecs[i]]);

        for (int i = 0; i < vec.size(); i ++){
            for (int j = i + 1; j < vec.size(); j ++){
                if (sibling[vec[i]][vec[j]]){
                    // cout << vec[i] << " and " << vec[j] << " are siblings" << endl;
                    good = 0;
                }
            }
        }

        if (!good){
            cout << "greska" << endl;
            continue;
        }

        cout << "ok" << endl;

        int cur = mp.size();
        mp[vecs[0]] = cur;

        for (int j : vec)
            derived[cur][j] = 1;

        for (int i = 0; i < cur; i ++)
            for (int j : vec)
                derived[cur][i] |= derived[j][i];

        for (int i = 0; i < cur; i ++){
            if (derived[cur][i]) continue;
            for (int j = 0; j < cur; j ++)
                if (derived[i][j] and derived[cur][j])
                    sibling[cur][i] = sibling[i][cur] = 1;
        }
    }
}

Compilation message (stderr)

dijament.cpp: In function 'int main()':
dijament.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 1; i < vecs.size(); i ++){
      |                         ~~^~~~~~~~~~~~~
dijament.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i = 1; i < vecs.size(); i ++)
      |                         ~~^~~~~~~~~~~~~
dijament.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i = 0; i < vec.size(); i ++){
      |                         ~~^~~~~~~~~~~~
dijament.cpp:47:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int j = i + 1; j < vec.size(); j ++){
      |                                 ~~^~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44