Submission #832338

#	Time	Username	Problem	Language	Result	Execution time	Memory
832338		finn__	Toy Train (IOI17_train)	C++17	16 / 100	9 ms	2004 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 5000;

vector<int> g[N], rg[N], postorder, scc[N], scc_non_charge[N];
bitset<N> visited, is_charging, f, deleted;
int ind[N];

void postorder_dfs(int u)
{
    visited[u] = 1;
    for (auto const &v : g[u])
        if (!visited[v] && !deleted[v])
            postorder_dfs(v);
    postorder.push_back(u);
}

void find_scc(int u, size_t s)
{
    visited[u] = 1;
    scc[s].push_back(u);
    ind[u] = s;
    for (auto const &v : rg[u])
        if (!visited[v])
            find_scc(v, s);
}

void find_scc_non_charge(int u, size_t s)
{
    visited[u] = 1;
    scc_non_charge[s].push_back(u);
    for (auto const &v : rg[u])
        if (!visited[v] && !deleted[v])
            find_scc(v, s);
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
    size_t const n = a.size(), m = u.size();
    int subtask = 1;
    for (size_t i = 0; i < m; ++i)
        if (u[i] != v[i] && u[i] + 1 != v[i])
        {
            subtask = 3;
            break;
        }

    vector<int> w(n);

    if (subtask == 1)
    {
        vector<bool> has_edge(n), has_loop(n);
        for (size_t i = 0; i < m; ++i)
        {
            if (u[i] == v[i])
                has_loop[u[i]] = 1;
            else
                has_edge[u[i]] = 1;
        }

        for (size_t i = 0; i < n; ++i)
        {
            for (size_t j = i; j < n; ++j)
                if (has_loop[j])
                {
                    if (!(a[j] ^ r[j]))
                    {
                        w[i] = a[j];
                        break;
                    }
                    if (!has_edge[j])
                    {
                        w[i] = !a[j];
                        break;
                    }
                }
        }

        return w;
    }

    for (size_t i = 0; i < n; ++i)
        is_charging[i] = r[i];
    for (size_t i = 0; i < m; ++i)
        g[u[i]].push_back(v[i]), rg[v[i]].push_back(u[i]);

    for (size_t i = 0; i < n; ++i)
        if (!visited[i])
            postorder_dfs(i);
    visited.reset();
    size_t s = 0;
    for (auto it = postorder.rbegin(); it != postorder.rend(); ++it)
        if (!visited[*it])
        {
            find_scc(*it, s++);
        }

    for (int &x : a)
        if (!x)
        {
            subtask = 4;
            break;
        }

    if (subtask == 3)
    {
        for (size_t i = 0; i < s; ++i)
        {
            bool has_charging_node = 0;
            for (int u : scc[i])
                has_charging_node |= r[u];
            bool has_cycle = scc[i].size() > 1;
            for (int u : scc[i])
                for (int v : g[u])
                    has_cycle |= u == v;
            if (has_cycle && has_charging_node)
            {
                f[i] = 1;
            }
        }
    }
    else
    {
        for (size_t i = 0; i < n; ++i)
            deleted[i] = r[i];
        visited.reset();
        postorder.clear();
        for (size_t i = 0; i < n; ++i)
            if (!visited[i] && !deleted[i])
                postorder_dfs(i);
        visited.reset();
        size_t t = 0;
        for (auto it = postorder.rbegin(); it != postorder.rend(); ++it)
            if (!visited[*it])
            {
                find_scc_non_charge(*it, t++);
            }

        for (size_t i = 0; i < t; ++i)
        {
            bool has_cycle = scc_non_charge[i].size() > 1;
            for (int u : scc_non_charge[i])
                for (int v : g[u])
                    has_cycle |= u == v;
            if (has_cycle)
            {
                f[ind[scc_non_charge[i][0]]] = 1;
            }
        }
    }

    for (size_t i = s - 1; i < s; --i)
        if (f[i])
        {
            for (auto const u : scc[i])
                for (auto const &v : rg[u])
                    f[ind[v]] = 1;
        }

    for (size_t i = 0; i < n; ++i)
        w[i] = f[ind[i]] ^ (subtask == 4);

    return w;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51