Submission #221508

#	Time	Username	Problem	Language	Result	Execution time	Memory
221508		emil_physmath	장난감 기차 (IOI17_train)	C++17	22 / 100	17 ms	1792 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;
    if (nei[v].empty())
        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);
}
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);
    if (!count(a, a + n, 0))
        return Solve3();
    if (!count(a, a + n, 1))
        return Solve4();
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < u.size(); ++i)
                     ~~^~~~~~~~~~
train.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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