oj.uz

Submission #40069

# Submission time Handle Problem Language Result Execution time Memory
40069 2018-01-26T10:57:08 Z krauch Dijamant (COI16_dijament) C++14
100 / 100
 377 ms 3320 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e3 + 6;

int n, sz;
bitset < N > par[N], bad[N];
map < string, int > mp;

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

	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    cin >> n;
    forn(i, 1, n) {
        string s;
        getline(cin, s);
        if (i == 1) getline(cin, s);

        int ptr = 0;
        string vname = "";
        bool fu = 0;
        while (s[ptr] != ' ') {
            vname += s[ptr];
            ++ptr;
        }
        ptr += 3;
        if (mp.count(vname)) fu = 1;

        vector < int > tmp;
        string toname = "";
        while (s[ptr] != ';') {
            if (s[ptr] == ' ') {
                if (!mp.count(toname)) fu = 1;
                else tmp.eb(mp[toname]);
                toname = "";
            }
            else {
                toname += s[ptr];
            }
            ++ptr;
        }

        if (fu) {
            cout << "greska\n";
            continue;
        }

        bitset < N > bit;
        for (auto it : tmp) {
            bit |= par[it];
        }
        forn(i, 1, sz) {
            if (!bit[i]) continue;
            if ((bad[i] & bit).count()) fu = 1;
        }
        if (fu) {
            cout << "greska\n";
            continue;
        }
        ++sz;
        mp[vname] = sz;
        par[sz] = bit;
        par[sz][sz] = 1;
        forn(i, 1, sz) {
            if (par[sz][i]) continue;
            if ((par[sz] & par[i]).count()) bad[sz][i] = 1;
        }
        cout << "ok\n";
    }

	return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
29.0 / 29.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 3320 KB Output is correct
2 Correct 377 ms 3320 KB Output is correct
3 Correct 74 ms 3188 KB Output is correct
4 Correct 11 ms 3188 KB Output is correct
5 Correct 40 ms 3188 KB Output is correct
6 Correct 27 ms 3188 KB Output is correct
7 Correct 69 ms 3188 KB Output is correct
8 Correct 71 ms 3188 KB Output is correct
9 Correct 51 ms 3188 KB Output is correct
10 Correct 24 ms 3188 KB Output is correct
11 Correct 35 ms 3188 KB Output is correct
12 Correct 297 ms 3320 KB Output is correct