oj.uz

Submission #268115

# Submission time Handle Problem Language Result Execution time Memory
268115 2020-08-16T08:53:27 Z kartel Dijamant (COI16_dijament) C++14
27 / 100
 2000 ms 28972 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 target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,nso-stack-protector,unroll-loops,fast-math,-O3")
#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;
    }
}

Compilation message

dijament.cpp:7:76: warning: bad option '-fnso-stack-protector' to pragma 'optimize' [-Wpragmas]
    7 | #pragma GCC optimize("Ofast,nso-stack-protector,unroll-loops,fast-math,-O3")
      |                                                                            ^
dijament.cpp:45:35: warning: bad option '-fnso-stack-protector' to attribute 'optimize' [-Wattributes]
   45 | void check_cycles(int v, bool &bad)
      |                                   ^
dijament.cpp:70:15: warning: bad option '-fnso-stack-protector' to attribute 'optimize' [-Wattributes]
   70 | void dfs(int v)
      |               ^
dijament.cpp:81:36: warning: bad option '-fnso-stack-protector' to attribute 'optimize' [-Wattributes]
   81 | void up(int v, bool &bad, bool &vis)
      |                                    ^
dijament.cpp:102:17: warning: bad option '-fnso-stack-protector' to attribute 'optimize' [-Wattributes]
  102 | void go_up(int v)
      |                 ^
dijament.cpp:113:10: warning: bad option '-fnso-stack-protector' to attribute 'optimize' [-Wattributes]
  113 | int main()
      |          ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 19 ms 28576 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 19 ms 28576 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 980 ms 28744 KB Output is correct
7 Correct 25 ms 28544 KB Output is correct
8 Correct 18 ms 28544 KB Output is correct
9 Correct 23 ms 28544 KB Output is correct
10 Correct 18 ms 28544 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 19 ms 28576 KB Output is correct
4 Correct 18 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 980 ms 28744 KB Output is correct
7 Correct 25 ms 28544 KB Output is correct
8 Correct 18 ms 28544 KB Output is correct
9 Correct 23 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 19 ms 28544 KB Output is correct
13 Correct 20 ms 28544 KB Output is correct
14 Correct 20 ms 28544 KB Output is correct
15 Correct 24 ms 28536 KB Output is correct
16 Correct 18 ms 28544 KB Output is correct
17 Correct 21 ms 28544 KB Output is correct
18 Execution timed out 2092 ms 28664 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 28972 KB Time limit exceeded
2 Halted 0 ms 0 KB -