Submission #575316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
575316	2022-06-10T07:44:17 Z	KoD	Toy Train (IOI17_train)	C++17	11 / 100	10 ms	1752 KB

train

#include "train.h"
#include <bits/stdc++.h>

using ll = long long;

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct fixed : private F {
    fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    const int n = a.size();
    const int m = u.size();
    vector<char> loop(n);
    vector<vector<int>> graph(n), rgraph(n);
    for (int i = 0; i < m; ++i) {
        if (u[i] == v[i]) {
            loop[u[i]] = true;
        }
        graph[u[i]].push_back(v[i]);
        rgraph[v[i]].push_back(u[i]);
    }
    vector<char> vis(n);
    vector<int> stack;
    for (int u = 0; u < n; ++u) {
        fixed([&](auto&& dfs, const int u) -> void {
            if (vis[u]) return;
            vis[u] = true;
            for (const int v : graph[u]) {
                dfs(v);
            }
            stack.push_back(u);
        })(u);
    }
    std::fill(vis.begin(), vis.end(), false);
    vector<vector<int>> group;
    while (!stack.empty()) {
        const int u = stack.back();
        stack.pop_back();
        if (vis[u]) continue;
        auto& list = group.emplace_back();
        fixed([&](auto&& dfs, const int u) -> void {
            if (vis[u]) return;
            vis[u] = true;
            for (const int v : rgraph[u]) {
                dfs(v);
            }
            list.push_back(u);
        })(u);
    }
    vector<int> ret(n);
    while (!group.empty()) {
        auto list = std::move(group.back());
        group.pop_back();
        if (list.size() == 1) {
            const int u = list[0];
            if (r[u] and loop[u]) {
                ret[u] = true;
            } else {
                for (const int v : graph[u]) {
                    if (ret[v]) {
                        ret[u] = true;
                    }
                }
            }
        } else {
            bool found = false;
            for (const int u : list) {
                for (const int v : graph[u]) {
                    if (ret[v]) {
                        ret[u] = true;
                    }
                }
                if (r[u] or ret[u]) {
                    found = true;
                }
            }
            if (found) {
                for (const int u : list) {
                    ret[u] = true;
                }
            }
        }
    }
    return ret;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	1492 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1748 KB	Output is correct
2	Correct	8 ms	1640 KB	Output is correct
3	Correct	7 ms	1620 KB	Output is correct
4	Correct	7 ms	1492 KB	Output is correct
5	Correct	9 ms	1720 KB	Output is correct
6	Correct	9 ms	1596 KB	Output is correct
7	Correct	10 ms	1620 KB	Output is correct
8	Correct	7 ms	1588 KB	Output is correct
9	Correct	7 ms	1492 KB	Output is correct
10	Correct	8 ms	1492 KB	Output is correct
11	Correct	7 ms	1512 KB	Output is correct
12	Correct	7 ms	1736 KB	Output is correct
13	Correct	8 ms	1716 KB	Output is correct
14	Correct	8 ms	1752 KB	Output is correct
15	Correct	8 ms	1748 KB	Output is correct
16	Correct	8 ms	1748 KB	Output is correct
17	Correct	8 ms	1644 KB	Output is correct
18	Correct	8 ms	1556 KB	Output is correct