oj.uz

답안 #268118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268118 2020-08-16T08:55:31 Z kartel Dijamant (COI16_dijament) C++14
27 / 100
 2000 ms 28976 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define pb push_back
#define N +300500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define Max_A int(1e9)
//#define el endl
#define pii pair <int, int>
#define piii pair <int, pair <int, int> >
#define psi pair <string, int>
#define err ld(1e-9)
#define Max_S int(3e6)
#define last(x) x.back()
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

map <string, int> mp;
int q, id;
string k, s;

int mrk[N];
bool mk[N];

vector <int> g[N], G[N], prd[N], pred[N];
vi vec1;

void check_cycles(int v, bool &bad)
{
    if (bad) return;

    if (mrk[v] == 1)
    {
        bad = 1;
        return;
    }
    if (mrk[v] == 2)
        return;

    mrk[v] = 1;

    for (auto u : G[v])
    {
        if (bad)
            return;

        check_cycles(u, bad);
    }

    mrk[v] = 2;
}

void dfs(int v)
{
    if (mrk[v])
        return;

    mrk[v] = 1;

    for (auto u : prd[v])
        dfs(u);
}

void up(int v, bool &bad, bool &vis)
{
    if (vis)
        return;

    if (mrk[v] == 2)
    {
        vis = 1;
        return;
    }

    if (mrk[v] == 1)
    {
        bad = 1;
        return;
    }

    for (auto u : prd[v])
        up(u, bad, vis);
}

void go_up(int v)
{
    if (mk[v])
        return;

    vec1.pb(v);
    mk[v] = 1;

    for (auto u : prd[v])
        go_up(u);
}
int main()
{
//    srand(time(0));
    cout.precision(3);
    cout << fixed;
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> q;
    id = 0;
    while (q--)
    {
        bool bad = 0, initdo = 0;
        cin >> k;

        if (mp.find(k) == mp.end())
            mp[k] = id++;
        else bad = 1, initdo = 1;

        vector <string> vec;

        cin >> s >> s;
        int kol = 0;

        while (s != ";")
        {
            kol++;
            vec.pb(s);

            if (mp.find(s) == mp.end())
                bad = 1;

            cin >> s;
        }
        sort(all(vec));
        int i = 1;
        while (i < sz(vec) && vec[i - 1] != vec[i]) i++;

        bad = (bad | (i < sz(vec)));

        if (!bad)
        {
            for (int i = 0; i < id; i++)
                G[i] = g[i], prd[i] = pred[i], mrk[i] = 0;

            for (auto s : vec)
            {
                prd[mp[k]].pb(mp[s]);
                G[mp[s]].pb(mp[k]);
            }

            for (int i = 0; i < id; i++)
                if (!mrk[i] && !bad && sz(prd[i]) == 0)
                    check_cycles(i, bad);

            if (!bad)
            {
                vec1.clear();
                for (int i = 0; i < id; i++)
                    mk[i] = 0;

                go_up(mp[k]);

                for (auto p : vec1)
                {
                    for (int i = 0; i < id; i++)
                        mrk[i] = 0;

                    mrk[p] = 2;

                    for (auto p1 : prd[p])
                        dfs(p1);

                    for (auto p1 : vec1)
                    {
                        if (p1 == p || mrk[p1] || bad)
                            continue;

                        for (auto p2 : prd[p1])
                        {
                            if (bad)
                                break;

                            if (mrk[p2])
                                continue;

                            bool vis = 0, old_bad = bad;
                            up(p2, bad, vis);

                            if (vis)
                                bad = old_bad;
                        }
                    }

                    if (bad)
                        break;
                }
            }
        }

        if (!bad)
        {
            for (auto s : vec)
            {
                pred[mp[k]].pb(mp[s]);
                g[mp[s]].pb(mp[k]);
            }
        }
        else if (!initdo)
            mp.erase(mp.find(k)), id--;

        cout << (bad ? "greska" : "ok") << el;
    }
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 18 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 18 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 21 ms 28544 KB Output is correct
6 Correct 990 ms 28920 KB Output is correct
7 Correct 27 ms 28664 KB Output is correct
8 Correct 20 ms 28544 KB Output is correct
9 Correct 18 ms 28544 KB Output is correct
10 Correct 18 ms 28544 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 18 ms 28544 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 21 ms 28544 KB Output is correct
6 Correct 990 ms 28920 KB Output is correct
7 Correct 27 ms 28664 KB Output is correct
8 Correct 20 ms 28544 KB Output is correct
9 Correct 18 ms 28544 KB Output is correct
10 Correct 18 ms 28544 KB Output is correct
11 Correct 18 ms 28544 KB Output is correct
12 Correct 18 ms 28544 KB Output is correct
13 Correct 19 ms 28544 KB Output is correct
14 Correct 20 ms 28544 KB Output is correct
15 Correct 26 ms 28544 KB Output is correct
16 Correct 20 ms 28544 KB Output is correct
17 Correct 19 ms 28544 KB Output is correct
18 Execution timed out 2090 ms 28544 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2039 ms 28976 KB Time limit exceeded
2 Halted 0 ms 0 KB -