oj.uz

답안 #268122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268122 2020-08-16T08:59:50 Z kartel Dijamant (COI16_dijament) C++14
56 / 100
 2000 ms 29056 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], mk1[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;
    }

    if (mk1[v])
        return;

    mk1[v] = 1;

    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;

                            for (int i = 0; i < id; i++)
                                mk1[i] = 0;

                            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 20 ms 28544 KB Output is correct
2 Correct 18 ms 28592 KB Output is correct
3 Correct 19 ms 28664 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 28544 KB Output is correct
2 Correct 18 ms 28592 KB Output is correct
3 Correct 19 ms 28664 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 985 ms 28664 KB Output is correct
7 Correct 26 ms 28544 KB Output is correct
8 Correct 19 ms 28544 KB Output is correct
9 Correct 19 ms 28544 KB Output is correct
10 Correct 19 ms 28544 KB Output is correct
11 Correct 18 ms 28636 KB Output is correct
12 Correct 20 ms 28704 KB Output is correct
13 Correct 19 ms 28544 KB Output is correct
14 Correct 19 ms 28544 KB Output is correct
15 Correct 21 ms 28672 KB Output is correct
16 Correct 19 ms 28544 KB Output is correct
17 Correct 19 ms 28544 KB Output is correct
18 Correct 38 ms 28544 KB Output is correct
19 Correct 20 ms 28544 KB Output is correct
20 Correct 19 ms 28544 KB Output is correct
21 Correct 19 ms 28544 KB Output is correct
22 Correct 18 ms 28544 KB Output is correct
23 Correct 19 ms 28544 KB Output is correct

Subtask #4
0 / 44.0

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