Submission #222125

#	Time	Username	Problem	Language	Result	Execution time	Memory
222125		emil_physmath	장난감 기차 (IOI17_train)	C++17	38 / 100	2082 ms	1784 KiB

train

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

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

vector<int> rnei[maxN];
void OK(vector<char>& mask)
{
    queue<int> cycle;
    for (int i = 0; i < n; ++i)
        if (mask[i])
            cycle.push(i);
    while (cycle.size())
    {
        int u = cycle.front();
        cycle.pop();
        if (!mask[u]) continue;
        bool g = false;
        if (a[u])
        {
            g = true;
            for (int to: nei[u])
                if (!mask[to] && ans[to] != 0)
                    g = false;
        }
        else
        {
            g = false;
            for (int to: nei[u])
                if (mask[to] || ans[to] == 0)
                    g = true;
        }
        if (!g)
        {
            mask[u] = 0;
            for (int to: rnei[u])
                if (mask[to])
                    cycle.push(to);
        }
    }
}
vector<int> Solve()
{
    for (int i = 0; i < n; ++i)
        ans[i] = 1;
    vector<char> stmask(n);
    for (int i = 0; i < n; ++i)
        if (!charge[i])
            stmask[i] = 1;
    while (true)
    {
        auto mask = stmask;
        OK(mask);
        if (!count(mask.begin(), mask.end(), 1))
            break;
        for (int i = 0; i < n; ++i)
            if (mask[i])
            {
                ans[i] = 0;
                stmask[i] = 0;
            }
        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, stmask[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);
    /*auto brutos = Brutos();
    cerr << "Brutos says:\t";
    for (int i: brutos)
        cerr << i << ' ';
    cerr << "\n\t\t";*/
    return Solve();
}

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:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < u.size(); ++i)
                     ~~^~~~~~~~~~

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