oj.uz

답안 #575315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
575315 2022-06-10T07:40:57 Z KoD 장난감 기차 (IOI17_train) C++17
11 / 100
 10 ms 1964 KB 
#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 (r[u] or 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 (r[u] or vis[u]) return;
            vis[u] = true;
            for (const int v : rgraph[u]) {
                dfs(v);
            }
            list.push_back(u);
        })(u);
    }
    vector<int> ret(n, 1);
    for (const auto& list : group) {
        if (list.size() == 1) {
            const int u = list[0];
            if (loop[u]) {
                ret[u] = 0;
            }
        } else {
            for (const int u : list) {
                ret[u] = 0;
            }
        }
    }
    std::fill(vis.begin(), vis.end(), false);
    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);
    group.clear();
    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);
    }
    while (!group.empty()) {
        auto list = std::move(group.back());
        group.pop_back();
        bool found = false;
        for (const int u : list) {
            for (const int v : graph[u]) {
                if (ret[v] == 0) {
                    ret[u] = 0;
                }
            }
            if (ret[u] == 0) {
                found = true;
            }
        }
        if (found) {
            for (const int u : list) {
                ret[u] = 0;
            }
        }
    }
    return ret;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1620 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1964 KB Output is correct
2 Correct 7 ms 1808 KB Output is correct
3 Correct 9 ms 1836 KB Output is correct
4 Incorrect 9 ms 1640 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1492 KB Output is correct
2 Correct 9 ms 1628 KB Output is correct
3 Correct 9 ms 1748 KB Output is correct
4 Correct 8 ms 1580 KB Output is correct
5 Correct 9 ms 1840 KB Output is correct
6 Correct 8 ms 1876 KB Output is correct
7 Correct 9 ms 1872 KB Output is correct
8 Correct 10 ms 1700 KB Output is correct
9 Correct 8 ms 1848 KB Output is correct
10 Correct 8 ms 1748 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 1876 KB Output is correct
13 Correct 9 ms 1748 KB Output is correct
14 Correct 8 ms 1724 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 1544 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1620 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -