제출 #222137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222137		emil_physmath	장난감 기차 (IOI17_train)	C++17	100 / 100	1922 ms	1792 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 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 OK(vector<char>& mask)
{
    queue<int> cycle;
    for (int i = 0; i < n; ++i)
        if (mask[i])
            cycle.push(i);
    int cnt = cycle.size();
    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)
        {
            --cnt;
            mask[u] = 0;
            for (int to: rnei[u])
                if (mask[to])
                    cycle.push(to);
        }
    }
    return cnt;
}
void Add(vector<char>& mask)
{
    queue<int> cycle;
    for (int i = 0; i < n; ++i)
        if (mask[i])
            for (int to: rnei[i])
                cycle.push(to);
    while (cycle.size())
    {
        int u = cycle.front();
        cycle.pop();
        if (!ans[u]) continue;
        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;
            for (int to: rnei[u])
                if (ans[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;
        if (!OK(mask))
            break;
        for (int i = 0; i < n; ++i)
            if (mask[i])
            {
                ans[i] = 0;
                stmask[i] = 0;
            }
        Add(mask);
    }
    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();
    return Solve();
}

컴파일 시 표준 에러 (stderr) 메시지

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:173: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: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51