Submission #1146553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146553		MtSaka	Toy Train (IOI17_train)	C++20	100 / 100	330 ms	1364 KiB

train

#include "train.h"

// #pragma GCC target "arch=icelake-server,prefer-vector-width=512"
// #pragma GCC optimize "Ofast"
#include <bits/stdc++.h>
#define overload(a, b, c, d, ...) d
#define rep1(n) for (ll _ = 0; _ < (ll)(n); ++_)
#define rep2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep3(i, l, r) for (ll i = (ll)(l); i < (ll)(r); ++i)
#define rep(...) overload(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define rrep2(i, l, r) for (ll i = (ll)(r) - 1; i >= (ll)(l); --i)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vvl = vector<vl>;
using vp = vector<pl>;
using i128 = __int128_t;
template <typename T, typename U>
inline bool chmax(T& a, const U& b) { return (a < b ? a = b, true : false); }
template <typename T, typename U>
inline bool chmin(T& a, const U& b) { return (a > b ? a = b, true : false); }
static constexpr ll inf = numeric_limits<ll>::max() / 2;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        os << *it;
        if (it != prev(v.end())) os << ' ';
    }
    return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T, typename U>
istream& operator>>(istream& is, pair<T, U>& p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
void print(const T& x) {
    cout << x << '\n';
}
template <typename Head, typename... Args>
void print(const Head& head, const Args&... args) {
    cout << head << ' ';
    print(args...);
}
template <typename T>
void dbg(const T& x) {
#ifndef EVAL
    cerr << x << endl;
#endif
}
template <typename Head, typename... Args>
void dbg(const Head& head, const Args&... args) {
#ifndef EVAL
    cerr << head << ' ';
    dbg(args...);
#endif
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    ll n = a.size();
    vvl rg(n);
    vl deg(n);
    rep(i, u.size()) {
        rg[v[i]].eb(u[i]);
        deg[u[i]]++;
    }
    vector<int> res(n, 1);
    while (true) {
        bool flag = false;
        vl ndeg = deg;
        auto dfs = [&](auto&& dfs, ll v) -> void {
            for (auto u : rg[v]) {
                ndeg[u]--;
                if (r[u] == 0 && ndeg[u] == 0) dfs(dfs, u);
            }
        };
        rep(i, n) if (a[i]) ndeg[i] = 1;
        rep(i, n) if (r[i] && res[i]) dfs(dfs, i);
        rep(i, n) if (r[i] && res[i] && ndeg[i] > 0) res[i] = false, flag = true;
        rep(i, n) if (ndeg[i] > 0) res[i] = false;
        if (!flag) break;
    }
    return res;
}

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