oj.uz

Submission #395615

# Submission time Handle Problem Language Result Execution time Memory
395615 2021-04-28T16:54:12 Z idk321 Toy Train (IOI17_train) C++11
16 / 100
 73 ms 3148 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 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 6 ms 1484 KB Output is correct
2 Correct 6 ms 1484 KB Output is correct
3 Correct 6 ms 1440 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 23 ms 1492 KB Output is correct
7 Correct 27 ms 1496 KB Output is correct
8 Correct 21 ms 1492 KB Output is correct
9 Correct 44 ms 1444 KB Output is correct
10 Correct 63 ms 1404 KB Output is correct
11 Correct 73 ms 1364 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 592 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 3020 KB Output is correct
2 Correct 11 ms 3020 KB Output is correct
3 Correct 11 ms 3060 KB Output is correct
4 Correct 12 ms 2996 KB Output is correct
5 Correct 12 ms 2892 KB Output is correct
6 Correct 12 ms 2636 KB Output is correct
7 Correct 13 ms 2696 KB Output is correct
8 Correct 13 ms 2752 KB Output is correct
9 Correct 11 ms 2508 KB Output is correct
10 Correct 12 ms 2508 KB Output is correct
11 Correct 11 ms 2464 KB Output is correct
12 Correct 11 ms 2448 KB Output is correct
13 Correct 12 ms 3148 KB Output is correct
14 Correct 12 ms 3116 KB Output is correct
15 Correct 12 ms 3124 KB Output is correct
16 Correct 12 ms 3136 KB Output is correct
17 Correct 12 ms 3148 KB Output is correct
18 Correct 7 ms 2000 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2124 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 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 6 ms 1484 KB Output is correct
2 Correct 6 ms 1484 KB Output is correct
3 Correct 6 ms 1440 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 23 ms 1492 KB Output is correct
7 Correct 27 ms 1496 KB Output is correct
8 Correct 21 ms 1492 KB Output is correct
9 Correct 44 ms 1444 KB Output is correct
10 Correct 63 ms 1404 KB Output is correct
11 Correct 73 ms 1364 KB Output is correct
12 Incorrect 1 ms 592 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -