oj.uz

Submission #395641

# Submission time Handle Problem Language Result Execution time Memory
395641 2021-04-28T17:33:57 Z idk321 Toy Train (IOI17_train) C++11
16 / 100
 70 ms 2932 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> adjIn[N];

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



bool miss[N];


int out[N];
int timer = 0;

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

vector<int> comps;

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

bool vis[N];
void dfs(int node)
{
    st.push_back(node);
    onSt[node] = true;
    vis[node] = true;

    for (int next : adj[node])
    {
        if (miss[next]) continue;

        if (!vis[next])
        {
            dfs(next);
        } else if (onSt[next])
        {
            int cur = st.size() - 1;
            while (true)
            {
                if (r[st[cur]] == 1) goodA[st[cur]] = true;
                goodB[st[cur]] = true;
                if (st[cur] == node) break;
                cur--;
            }
        }
    }

    onSt[node] = false;
    st.pop_back();
}




bool reachable[N];
void goReach(int node)
{
    reachable[node] = true;
    for (int next : adjIn[node])
    {
        if (reachable[next]) continue;
        goReach(next);
    }
}


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]);
        adjIn[v[i]].push_back(u[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 (!vis[i]) dfs(i);
        }

        for (int i = 0; i < n; i++)
        {
            if (goodA[i] && !reachable[i]) goReach(i);
        }
        for (int i = 0; i < n; i++) res[i] = reachable[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] && !vis[i]) dfs(i);
        }

        for (int i = 0; i < n; i++)
        {
            if (goodB[i] && !reachable[i]) goReach(i);
        }

        for (int i = 0; i < n; i++)
        {
            res[i] = !reachable[i];
        }

        return res;
    }

	return res;
}

/*
10 11
0 0 0 0 0 0 0 0 0 0
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
8 9
9 8
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1484 KB Output is correct
2 Correct 6 ms 1400 KB Output is correct
3 Correct 6 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 14 ms 1484 KB Output is correct
6 Correct 29 ms 1476 KB Output is correct
7 Correct 27 ms 1484 KB Output is correct
8 Correct 21 ms 1484 KB Output is correct
9 Correct 46 ms 1452 KB Output is correct
10 Correct 62 ms 1420 KB Output is correct
11 Correct 70 ms 1364 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 660 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 12 ms 2932 KB Output is correct
2 Correct 11 ms 2892 KB Output is correct
3 Correct 11 ms 2892 KB Output is correct
4 Correct 12 ms 2764 KB Output is correct
5 Correct 12 ms 2716 KB Output is correct
6 Correct 12 ms 2596 KB Output is correct
7 Correct 14 ms 2632 KB Output is correct
8 Incorrect 30 ms 2628 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2072 KB Output is correct
2 Correct 13 ms 2288 KB Output is correct
3 Correct 13 ms 2592 KB Output is correct
4 Correct 12 ms 2620 KB Output is correct
5 Correct 12 ms 2584 KB Output is correct
6 Correct 12 ms 2568 KB Output is correct
7 Correct 11 ms 2508 KB Output is correct
8 Correct 12 ms 2428 KB Output is correct
9 Correct 10 ms 2380 KB Output is correct
10 Correct 12 ms 2652 KB Output is correct
11 Correct 11 ms 2596 KB Output is correct
12 Correct 11 ms 2544 KB Output is correct
13 Correct 16 ms 2724 KB Output is correct
14 Correct 11 ms 2380 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2508 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 8 ms 1484 KB Output is correct
2 Correct 6 ms 1400 KB Output is correct
3 Correct 6 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 14 ms 1484 KB Output is correct
6 Correct 29 ms 1476 KB Output is correct
7 Correct 27 ms 1484 KB Output is correct
8 Correct 21 ms 1484 KB Output is correct
9 Correct 46 ms 1452 KB Output is correct
10 Correct 62 ms 1420 KB Output is correct
11 Correct 70 ms 1364 KB Output is correct
12 Incorrect 1 ms 660 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -