Submission #222078

#	Time	Username	Problem	Language	Result	Execution time	Memory
222078		emil_physmath	Toy Train (IOI17_train)	C++17	0 / 100	2095 ms	1536 KiB

train

#include "train.h"
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxN = 5000;

vector<int> nei[maxN];
int charge[maxN], a[maxN];
int ans[maxN];
int col[maxN], isCyc[maxN];
int n;

vector<int> rnei[maxN];
bool used1[maxN];
void DFS1(int v, vector<int>& sorted)
{
    used1[v] = true;
    for (int to: nei[v])
        if (!used1[to])
            DFS1(to, sorted);
    sorted.push_back(v);
}
void DFS2(int v, int curcol)
{
    col[v] = curcol;
    for (int to: rnei[v])
        if (!col[to])
        {
            DFS2(to, curcol);
            isCyc[curcol] = true;
        }
        else if (col[to] == curcol)
            isCyc[curcol] = true;
}
void SCC()
{
    vector<int> sorted;
    for (int i = 0; i < n; ++i)
        if (!used1[i])
            DFS1(i, sorted);
    reverse(sorted.begin(), sorted.end());
    int cols = 0;
    for (int v: sorted)
        if (!col[v])
            DFS2(v, ++cols);
}
bool used3[maxN];
void DFS3(int v)
{
    used3[v] = true;
    ans[v] = 1;
    for (int to: rnei[v])
        if (!used3[to])
            DFS3(to);
}
vector<int> Solve3()
{
    SCC();
    vector<bool> goodcol(n);
    for (int v = 0; v < n; ++v)
        if (charge[v])
            goodcol[col[v]] = true;
    for (int v = 0; v < n; ++v)
        if (goodcol[col[v]] && isCyc[col[v]] && !used3[v])
            DFS3(v);
    return vector<int>(ans, ans + n);
}
bool used4[maxN];
int DFS4(int v)
{
    static set<int> cur;
    cur.insert(v);
    used4[v] = true;
    for (int to: nei[v])
        if (!used4[to] && !charge[to])
            isCyc[v] = max(isCyc[v], DFS4(to));
        else if (cur.count(to))
            isCyc[v] = 1;
    cur.erase(v);
    return isCyc[v];
}
vector<int> Solve4()
{
    for (int v = 0; v < n; ++v)
        if (!used3[v] && !charge[v])
            DFS4(v);
    for (int v = 0; v < n; ++v)
        if (!used3[v] && isCyc[v])
            DFS3(v);
    for (int v = 0; v < n; ++v)
        ans[v] = (ans[v] ? 0 : 1);
    return vector<int>(ans, ans + n);
}
vector<int> Solve1()
{
    vector<bool> loop(n), isend(n, true);
    for (int v = 0; v < n; ++v)
    {
        for (int to: nei[v])
            if (v == to)
                loop[v] = true;
            else
                isend[v] = false;
        loop[v] = max(loop[v], isend[v]);
    }
    for (int i = 0, st = 0; i < n; ++i)
    {
        if (loop[i] && charge[i] && a[i] || isend[i] && charge[i])
        {
            for (int j = st; j <= i; ++j)
                ans[j] = 1;
            st = i + 1;
        }
        else if (loop[i] && !charge[i] && !a[i] || isend[i] && !charge[i])
        {
            for (int j = st; j <= i; ++j)
                ans[j] = 0;
            st = i + 1;
        }
    }
    return vector<int>(ans, ans + n);
}
int OK(int mask)
{
    vector<int> cycle;
    for (int i = 0; i < n; ++i)
        if (mask & (1 << i))
        {
            if (charge[i])
                return i;
            else
                cycle.push_back(i);
        }
    for (int u: cycle)
    {
        bool g = false;
        if (a[u])
        {
            g = true;
            for (int to: nei[u])
                if (!count(cycle.begin(), cycle.end(), to) && ans[to] != 0)
                    g = false;
        }
        else
        {
            g = false;
            for (int to: nei[u])
                if (count(cycle.begin(), cycle.end(), to) || ans[to] == 0)
                    g = true;
        }
        if (!g) return u;
    }
    return -1;
}
vector<int> Solve()
{
    for (int i = 0; i < n; ++i)
        ans[i] = 1;
    while (true)
    {
        int mask = (1 << n) - 1;
        int u = -1;
        while ((u = OK(mask)) != -1)
            mask ^= (1 << u);
        bool brk = true;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i))
                ans[i] = 0, brk = false;
        if (brk) break;
        for (int i = 0; i < n; ++i)
            for (int u = 0; u < n; ++u)
            {
                bool g = false;
                if (a[u])
                {
                    g = true;
                    for (int to: nei[u])
                        if (ans[to] != 0)
                            g = false;
                }
                else
                {
                    g = false;
                    for (int to: nei[u])
                        if (ans[to] == 0)
                            g = true;
                }
                if (g)
                    ans[u] = 0;
            }
    }
    return vector<int>(ans, ans + n);
}
std::vector<int> who_wins(std::vector<int> a_, std::vector<int> charge_, std::vector<int> u, std::vector<int> v) {
    n = a_.size();
    for (int i = 0; i < n; ++i)
        a[i] = a_[i], charge[i] = charge_[i];
    for (int i = 0; i < u.size(); ++i)
        nei[u[i]].push_back(v[i]);
    for (int v = 0; v < n; ++v)
        for (int to: nei[v])
            rnei[to].push_back(v);
    return Solve();
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> Solve1()':
train.cpp:109:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (loop[i] && charge[i] && a[i] || isend[i] && charge[i])
             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
train.cpp:115:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         else if (loop[i] && !charge[i] && !a[i] || isend[i] && !charge[i])
                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:199:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < u.size(); ++i)
                     ~~^~~~~~~~~~

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