oj.uz

Submission #395617

# Submission time Handle Problem Language Result Execution time Memory
395617 2021-04-28T17:00:45 Z idk321 Toy Train (IOI17_train) C++11
27 / 100
 76 ms 2900 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 in[N];
int up[N];
int out[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 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 (!in[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] && !in[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 7 ms 1356 KB Output is correct
2 Correct 6 ms 1356 KB Output is correct
3 Correct 6 ms 1356 KB Output is correct
4 Correct 8 ms 1356 KB Output is correct
5 Correct 14 ms 1424 KB Output is correct
6 Correct 23 ms 1416 KB Output is correct
7 Correct 32 ms 1404 KB Output is correct
8 Correct 21 ms 1356 KB Output is correct
9 Correct 44 ms 1364 KB Output is correct
10 Correct 64 ms 1324 KB Output is correct
11 Correct 76 ms 1228 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2900 KB Output is correct
2 Correct 11 ms 2772 KB Output is correct
3 Correct 11 ms 2764 KB Output is correct
4 Correct 12 ms 2868 KB Output is correct
5 Correct 12 ms 2772 KB Output is correct
6 Correct 12 ms 2540 KB Output is correct
7 Correct 14 ms 2380 KB Output is correct
8 Correct 12 ms 2508 KB Output is correct
9 Correct 11 ms 2380 KB Output is correct
10 Correct 12 ms 2376 KB Output is correct
11 Correct 11 ms 2272 KB Output is correct
12 Correct 13 ms 2188 KB Output is correct
13 Correct 12 ms 2844 KB Output is correct
14 Correct 16 ms 2892 KB Output is correct
15 Correct 13 ms 2892 KB Output is correct
16 Correct 12 ms 2892 KB Output is correct
17 Correct 15 ms 2892 KB Output is correct
18 Correct 7 ms 1868 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1996 KB Output is correct
2 Correct 11 ms 2340 KB Output is correct
3 Correct 15 ms 2604 KB Output is correct
4 Correct 16 ms 2636 KB Output is correct
5 Correct 14 ms 2636 KB Output is correct
6 Correct 12 ms 2652 KB Output is correct
7 Correct 12 ms 2592 KB Output is correct
8 Correct 12 ms 2508 KB Output is correct
9 Correct 10 ms 2380 KB Output is correct
10 Correct 13 ms 2588 KB Output is correct
11 Correct 11 ms 2636 KB Output is correct
12 Correct 11 ms 2684 KB Output is correct
13 Correct 12 ms 2848 KB Output is correct
14 Correct 11 ms 2560 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2380 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 7 ms 1356 KB Output is correct
2 Correct 6 ms 1356 KB Output is correct
3 Correct 6 ms 1356 KB Output is correct
4 Correct 8 ms 1356 KB Output is correct
5 Correct 14 ms 1424 KB Output is correct
6 Correct 23 ms 1416 KB Output is correct
7 Correct 32 ms 1404 KB Output is correct
8 Correct 21 ms 1356 KB Output is correct
9 Correct 44 ms 1364 KB Output is correct
10 Correct 64 ms 1324 KB Output is correct
11 Correct 76 ms 1228 KB Output is correct
12 Incorrect 1 ms 588 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -