oj.uz

답안 #268100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268100 2020-08-16T08:41:52 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 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];

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

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);
}

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)
            {
                for (auto p : prd[mp[k]])
                {
                    for (int i = 0; i < id; i++)
                        mrk[i] = 0;

                    mrk[p] = 2;

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

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

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

                            if (mrk[p2])
                                continue;

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

                            if (vis)
                                bad = 0;
                        }
                    }

                    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 19 ms 28544 KB Output is correct
3 Correct 18 ms 28532 KB Output is correct
4 Correct 23 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 19 ms 28544 KB Output is correct
3 Correct 18 ms 28532 KB Output is correct
4 Correct 23 ms 28544 KB Output is correct
5 Correct 18 ms 28544 KB Output is correct
6 Correct 1213 ms 28976 KB Output is correct
7 Correct 30 ms 28544 KB Output is correct
8 Correct 19 ms 28544 KB Output is correct
9 Correct 19 ms 28672 KB Output is correct
10 Correct 19 ms 28544 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 28544 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 18 ms 28532 KB Output is correct
4 Correct 23 ms 28544 KB Output is correct
5 Correct 18 ms 28544 KB Output is correct
6 Correct 1213 ms 28976 KB Output is correct
7 Correct 30 ms 28544 KB Output is correct
8 Correct 19 ms 28544 KB Output is correct
9 Correct 19 ms 28672 KB Output is correct
10 Correct 19 ms 28544 KB Output is correct
11 Correct 19 ms 28544 KB Output is correct
12 Correct 19 ms 28544 KB Output is correct
13 Incorrect 19 ms 28544 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

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