oj.uz

Submission #395610

# Submission time Handle Problem Language Result Execution time Memory
395610 2021-04-28T16:45:15 Z idk321 Toy Train (IOI17_train) C++11
5 / 100
 2000 ms 2800 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5000;
set<int> adj[N];

vector<int> a;
vector<int> r;
vector<int> u;
vector<int> v;



bool miss[N];

int in[N];
int up[N];
int timer = 0;

bool goodA[N];
bool goodB[N];

vector<int> comps;

vector<int> st;
bool onSt[N];

void dfs(int node)
{
    timer++;
    in[node] = timer;
    up[node] = in[node];
    st.push_back(node);
    onSt[node] = true;
    for (int next : adj[node])
    {
        if (miss[next]) continue;
        if (next == node && r[node])
        {
            goodA[node] = true;
        }
        if (next == node) goodB[node] = true;

        if (in[next] == 0)
        {
            dfs(next);
            up[node] = min(up[node], up[next]);
        } else if (onSt[next])
        {
            up[node] = min(up[node], in[next]);
        }
    }

    if (in[node] == up[node])
    {
        vector<int> comp;
        while (st.back() != node)
        {
            onSt[st.back()] = false;
            if (r[st.back()]) goodA[st.back()] = true;
            goodB[st.back()] = true;
            comp.push_back(st.back());
            st.pop_back();
        }
        comp.push_back(node);
        st.pop_back();
        onSt[node] = false;
        if (comp.size() > 1 && r[node])
        {
            goodA[node] = true;
        }
        if (comp.size() > 1) goodB[node] = true;
    }
}

bool vis[N];

bool reachGoodA(int node)
{
    if (goodA[node]) return true;
    vis[node] = true;

    bool ok = false;
    for (int next : adj[node])
    {
        if (vis[next]) continue;
        ok = ok || reachGoodA(next);
    }

    return ok;
}

bool reachGoodB(int node)
{
    if (goodB[node]) return true;
    vis[node] = true;

    bool ok = false;
    for (int next : adj[node])
    {
        if (vis[next]) continue;
        ok = ok || reachGoodB(next);
    }

    return ok;
}

std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> U, std::vector<int> V) {
    a = A;
    r = R;
    u = U;
    v = V;

    int n = a.size();
    int m = u.size();
    bool simple = true;
    for (int i = 0; i < m; i++)
    {
        if (!(v[i] == u[i] || v[i] == u[i] + 1)) simple = false;
        adj[u[i]].insert(v[i]);
    }

    std::vector<int> res(a.size());


    bool allA = true;
    bool allB = true;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == 1) allB = false;
        if (a[i] == 0) allA = false;
    }
    //cout << simple << endl;
    if (simple)
    {
        for (int i = 0; i < n; i++)
        {
            int cur = i;
            bool good = false;
            int travelled = 0;
            while (travelled < n)
            {
                if (a[cur] == 1)
                {
                    if (r[cur] == 1)
                    {
                        if (adj[cur].find(cur) != adj[cur].end())
                        {
                            good = true;
                            break;
                        }
                    }

                    for (int next : adj[cur])
                    {
                        if (next != cur)
                        {
                            cur = next;
                            break;
                        }
                    }
                } else
                {
                    if (r[cur] != 1)
                    {
                        if (adj[cur].find(cur) != adj[cur].end())
                        {
                            break;
                        }
                    }

                    for (int next : adj[cur])
                    {
                        if (next != cur)
                        {
                            cur = next;
                            break;
                        }
                    }
                }

                travelled++;
            }

            if (r[cur]) good = true;
            res[i] = good;
        }

        return res;
    } else if (allA)
    {
        for (int i = 0; i < n; i++)
        {
            if (!in[i]) dfs(i);
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < N; j++) vis[j] = false;
             res[i] = reachGoodA(i);
        }

        return res;
    } else if (allB)
    {
        for (int i = 0; i < n; i++) if (r[i]) miss[i] = true;

        for (int i = 0; i < n; i++)
        {
            if (!miss[i] && !in[i]) dfs(i);
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < N; j++) vis[j] = false;
             res[i] = reachGoodB(i);

        }

        return res;
    }

	return res;
}

/*
10 12
1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 1 0 0 0
0 1
1 2
2 1
1 3
1 4
4 5
5 4
6 6
7 7
3 3
8 9
9 8
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 5 ms 1148 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 7 ms 1100 KB Output is correct
5 Correct 12 ms 1156 KB Output is correct
6 Correct 25 ms 1148 KB Output is correct
7 Correct 31 ms 1140 KB Output is correct
8 Correct 27 ms 1144 KB Output is correct
9 Correct 45 ms 1120 KB Output is correct
10 Correct 63 ms 1080 KB Output is correct
11 Correct 69 ms 1016 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 2524 KB Output is correct
2 Correct 353 ms 2500 KB Output is correct
3 Correct 381 ms 2488 KB Output is correct
4 Correct 23 ms 2508 KB Output is correct
5 Correct 280 ms 2500 KB Output is correct
6 Correct 1397 ms 2188 KB Output is correct
7 Correct 24 ms 2244 KB Output is correct
8 Correct 355 ms 2160 KB Output is correct
9 Correct 868 ms 2252 KB Output is correct
10 Correct 298 ms 2272 KB Output is correct
11 Correct 406 ms 2200 KB Output is correct
12 Correct 70 ms 2124 KB Output is correct
13 Execution timed out 2033 ms 2800 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1802 ms 1868 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1996 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 5 ms 1148 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 7 ms 1100 KB Output is correct
5 Correct 12 ms 1156 KB Output is correct
6 Correct 25 ms 1148 KB Output is correct
7 Correct 31 ms 1140 KB Output is correct
8 Correct 27 ms 1144 KB Output is correct
9 Correct 45 ms 1120 KB Output is correct
10 Correct 63 ms 1080 KB Output is correct
11 Correct 69 ms 1016 KB Output is correct
12 Incorrect 1 ms 460 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -