제출 #221504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221504		emil_physmath	장난감 기차 (IOI17_train)	C++17	11 / 100	15 ms	1920 KiB

train

#include "train.h"
#include <algorithm>
#include <vector>
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()
{
    for (int v = 0; v < n; ++v)
        for (int to: nei[v])
            rnei[to].push_back(v);
    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);
}
vector<int> Solve4()
{
    SCC();
}
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]);
    if (!count(a, a + n, 0))
        return Solve3();
}

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

train.cpp: In function 'std::vector<int> Solve4()':
train.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < u.size(); ++i)
                     ~~^~~~~~~~~~
train.cpp:83: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: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51