oj.uz

답안 #707921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707921 2023-03-10T13:42:57 Z Cyanmond 장난감 기차 (IOI17_train) C++17
39 / 100
 2000 ms 224968 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    const int n = (int)a.size(), m = (int)u.size();
    std::vector<std::vector<int>> graph(n);
    for (int i = 0; i < m; ++i) {
        graph[u[i]].push_back(v[i]);
    }
    int cntC = 0;
    int chargingS = -1;
    for (int i = 0; i < n; ++i) {
        if (r[i] == 1) {
            ++cntC;
            if (chargingS == -1) {
                chargingS = i;
            }
        }
    }
    if (cntC == 1) {
        // subtask 5
        std::vector<int> reachableV(n, -1);
        reachableV[chargingS] = 1;
        for (int i = 0; i < n; ++i) {
            auto itr = std::find(graph[i].begin(), graph[i].end(), i);
            if (r[i] == 0 and a[i] == 0 and itr != graph[i].end()) {
                reachableV[i] = 0;
            }
        }
        for (int x = 0; x < 2 * n; ++x) {
            for (int i = 0; i < n; ++i) {
                if (reachableV[i] != -1) {
                    continue;
                }
                if (a[i] == 1) {
                    bool isOk = false, isRa = true;
                    for (const int t : graph[i]) {
                        if (reachableV[t] == 1) {
                            isOk = true;
                        }
                        if (reachableV[t] == -1) {
                            isRa = false;
                        }
                    }
                    if (isOk) {
                        reachableV[i] = 1;
                    } else if (isRa) {
                        reachableV[i] = 0;
                    }
                } else {
                    bool isOk = true, isRa = true;
                    for (const int t : graph[i]) {
                        if (reachableV[t] != 1) {
                            isOk = false;
                        }
                        if (reachableV[t] == -1) {
                            isRa = false;
                        }
                    }
                    if (isOk) {
                        reachableV[i] = 1;
                    } else if (isRa) {
                        reachableV[i] = 0;
                    }
                }
            }
        }
        for (auto &e : reachableV) {
            if (e == -1) {
                e = 0;
            }
        }
        reachableV[chargingS] = -1;
        if (a[chargingS] == 1) {
            bool isOk = false;
            for (const int t : graph[chargingS]) {
                if (reachableV[t] == 1) {
                    isOk = true;
                } else if (t == chargingS) {
                    isOk = true;
                }
            }
            if (isOk) {
                reachableV[chargingS] = 1;
            } else {
                reachableV[chargingS] = 0;
            }
        } else {
            bool isOk = true;
            for (const int t : graph[chargingS]) {
                if (reachableV[t] == 0) {
                    isOk = false;
                }
            }
            if (isOk) {
                reachableV[chargingS] = 1;
            } else {
                reachableV[chargingS] = 0;
            }
        }
    
        std::vector<int> answer(n);
        for (int i = 0; i < n; ++i) {
            answer[i] = (reachableV[i] == 1 and reachableV[chargingS] == 1) ? 1 : 0;
        }
        return answer;
    } else if (std::all_of(a.begin(), a.end(), [](const int v) {
        return v == 0;
    })) {
        // subtask 4
        std::vector<int> answer(n, 1);
        std::vector<bool> tCycle(n);
        for (int f = 0; f < n; ++f) {
            std::vector<int> type(n);
            auto dfs = [&](auto &&self, const int v) -> bool {
                type[v] = 1;
                for (const int t : graph[v]) {
                    if (r[t] == 1) {
                        continue;
                    }
                    if (type[t] == 0) {
                        const auto res = self(self, t);
                        if (res) {
                            return true;
                        }
                    } else if (type[t] == 1) {
                        return true;
                    }
                }
                type[v] = 2;
                return false;
            };
            tCycle[f] = dfs(dfs, f);
        }
        std::vector<std::vector<bool>> isReachable(n, std::vector<bool>(n));
        for (int f = 0; f < n; ++f) {
            isReachable[f][f] = true;
            std::queue<int> que;
            que.push(f);
            while (not que.empty()) {
                const int x = que.front();
                que.pop();
                for (const int t : graph[x]) {
                    if (not isReachable[f][t]) {
                        isReachable[f][t] = true;
                        que.push(t);
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isReachable[i][j] and tCycle[j]) {
                    answer[i] = 0;
                }
            }
        }
        return answer;
    } else if (std::all_of(a.begin(), a.end(), [](const int v) {
        return v == 1;
    })) {
        // subtask 3
        std::vector<int> answer(n);
        std::vector<bool> tCycle(n);
        for (int f = 0; f < n; ++f) {
            if (r[f] == 0) {
                continue;
            }
            std::vector<int> type(n);
            auto dfs = [&](auto &&self, const int v) -> bool {
                type[v] = 1;
                for (const int t : graph[v]) {
                    if (type[t] == 0) {
                        const auto res = self(self, t);
                        if (res) {
                            return true;
                        }
                    } else if (t == f) {
                        return true;
                    }
                }
                type[v] = 2;
                return false;
            };
            tCycle[f] = dfs(dfs, f);
        }
        std::vector<std::vector<bool>> isReachable(n, std::vector<bool>(n));
        for (int f = 0; f < n; ++f) {
            isReachable[f][f] = true;
            std::queue<int> que;
            que.push(f);
            while (not que.empty()) {
                const int x = que.front();
                que.pop();
                for (const int t : graph[x]) {
                    if (not isReachable[f][t]) {
                        isReachable[f][t] = true;
                        que.push(t);
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isReachable[i][j] and tCycle[j]) {
                    answer[i] = 1;
                }
            }
        }
        return answer;
    } else if (n <= 15) {
        // subtask 2
        std::vector<int> pow3(n + 1);
        pow3[0] = 1;
        for (int i = 1; i <= n; ++i) {
            pow3[i] = pow3[i - 1] * 3;
        }
        std::vector<int> graphBit(n);
        for (int i = 0; i < n; ++i) {
            int b = 0;
            for (const int t : graph[i]) {
                b |= 1 << t;
            }
            graphBit[i] = b;
        }
        std::vector<std::vector<char>> dp(n, std::vector<char>(pow3[n]));
        
        for (int bits = pow3[n] - 1; bits >= 0; --bits) {
            static std::vector<int> status(n);
            int bit1 = 0, bit2 = 0, bit3 = 0, bit4 = 0;
            int qbits = bits;
            auto nextBits = [&](const int a) {
                assert(status[a] == 0);
                int res = bits;
                res += pow3[a];
                if (r[a] == 1) {
                    res = qbits + 2 * pow3[a];
                }
                return res;
            };
            for (int i = 0; i < n; ++i) {
                const int v = bits % pow3[i + 1];
                const int c = v / pow3[i];
                status[i] = c;
            }
            for (int i = 0; i < n; ++i) {
                if (status[i] == 1) {
                    qbits += pow3[i];
                }
            }
            for (int i = 0; i < n; ++i) {
                const int c = status[i];
                if (c == 1) {
                    bit1 |= 1 << i;
                } else if (c == 2) {
                    bit2 |= 1 << i;
                } else {
                    if (dp[i][nextBits(i)]) {
                        bit3 |= 1 << i;
                    } else {
                        bit4 |= 1 << i;
                    }
                }
            }
            for (int f = 0; f < n; ++f) {
                if (status[f] == 0) {
                    continue;
                }
                if (a[f] == 1) {
                    bool isOk = false;
                    isOk |= (bit2 && graphBit[f]);
                    isOk |= (bit3 && graphBit[f]);
                    dp[f][bits] = isOk;
                } else {
                    bool isOk = true;
                    if (bit1 && graphBit[f]) {
                        isOk = false;
                    } else if (bit4 && graphBit[f]) {
                        isOk = false;
                    }
                    dp[f][bits] = isOk;
                }
            }
        }
        
        std::vector<int> answer(n);
        for (int i = 0; i < n; ++i) {
            answer[i] = dp[i][pow3[i] * (r[i] + 1)] ? 1 : 0;
        }
        return answer;
    } else {
        // subtask 1
        std::vector<int> answer(n);
        for (int i = 0; i < n; ++i) {
            int now = i;
            while (true) {
                if (a[now] == 1) {
                    if (r[now] == 1 and std::find(graph[now].begin(), graph[now].end(), now) != graph[now].end()) {
                        answer[i] = 1;
                        break;
                    }
                    if (graph[now].size() == 1 and graph[now][0] == now) {
                        answer[i] = 0;
                        break;
                    }
                    ++now;
                } else {
                    if (r[now] == 0 and std::find(graph[now].begin(), graph[now].end(), now) != graph[now].end()) {
                        answer[i] = 0;
                        break;
                    }
                    if (graph[now].size() == 1 and graph[now][0] == now) {
                        answer[i] = 1;
                        break;
                    }
                    ++now;
                }
            }
        }
        return answer;
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 34 ms 4076 KB Output is correct
8 Correct 25 ms 4180 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 788 KB Output is correct
11 Correct 3 ms 724 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 224968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 4308 KB Output is correct
2 Correct 276 ms 4308 KB Output is correct
3 Correct 275 ms 4460 KB Output is correct
4 Correct 984 ms 4444 KB Output is correct
5 Correct 664 ms 4296 KB Output is correct
6 Correct 572 ms 4256 KB Output is correct
7 Correct 732 ms 4228 KB Output is correct
8 Correct 381 ms 4256 KB Output is correct
9 Correct 521 ms 992 KB Output is correct
10 Correct 446 ms 4308 KB Output is correct
11 Correct 380 ms 4232 KB Output is correct
12 Correct 56 ms 4304 KB Output is correct
13 Correct 40 ms 1036 KB Output is correct
14 Correct 40 ms 1044 KB Output is correct
15 Correct 41 ms 1020 KB Output is correct
16 Correct 40 ms 980 KB Output is correct
17 Correct 40 ms 980 KB Output is correct
18 Correct 441 ms 4124 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 726 ms 4180 KB Output is correct
2 Correct 281 ms 4164 KB Output is correct
3 Correct 371 ms 4308 KB Output is correct
4 Correct 553 ms 4308 KB Output is correct
5 Correct 653 ms 4284 KB Output is correct
6 Correct 634 ms 4232 KB Output is correct
7 Correct 662 ms 4424 KB Output is correct
8 Correct 406 ms 4308 KB Output is correct
9 Correct 64 ms 4308 KB Output is correct
10 Correct 880 ms 4308 KB Output is correct
11 Correct 825 ms 4308 KB Output is correct
12 Correct 845 ms 4308 KB Output is correct
13 Correct 810 ms 1024 KB Output is correct
14 Correct 503 ms 960 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 744 ms 1020 KB Output is correct
2 Correct 45 ms 1036 KB Output is correct
3 Correct 337 ms 1028 KB Output is correct
4 Correct 43 ms 972 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 295 ms 744 KB Output is correct
7 Correct 22 ms 752 KB Output is correct
8 Correct 35 ms 768 KB Output is correct
9 Correct 33 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 10 ms 596 KB Output is correct

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 34 ms 4076 KB Output is correct
8 Correct 25 ms 4180 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 4 ms 788 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Execution timed out 2083 ms 224968 KB Time limit exceeded
13 Halted 0 ms 0 KB -