oj.uz

답안 #707920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707920 2023-03-10T13:42:19 Z Cyanmond 장난감 기차 (IOI17_train) C++17
39 / 100
 2000 ms 224876 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) {
            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 724 KB Output is correct
2 Correct 5 ms 844 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 824 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 26 ms 4184 KB Output is correct
8 Correct 25 ms 4180 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 3 ms 724 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 4440 KB Output is correct
2 Correct 264 ms 4456 KB Output is correct
3 Correct 275 ms 4580 KB Output is correct
4 Correct 962 ms 4572 KB Output is correct
5 Correct 673 ms 4424 KB Output is correct
6 Correct 568 ms 4432 KB Output is correct
7 Correct 739 ms 4356 KB Output is correct
8 Correct 366 ms 4436 KB Output is correct
9 Correct 559 ms 1116 KB Output is correct
10 Correct 448 ms 4436 KB Output is correct
11 Correct 368 ms 4436 KB Output is correct
12 Correct 48 ms 4436 KB Output is correct
13 Correct 43 ms 1160 KB Output is correct
14 Correct 44 ms 1152 KB Output is correct
15 Correct 40 ms 1160 KB Output is correct
16 Correct 41 ms 1164 KB Output is correct
17 Correct 52 ms 1068 KB Output is correct
18 Correct 440 ms 4248 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 734 ms 4336 KB Output is correct
2 Correct 264 ms 4296 KB Output is correct
3 Correct 359 ms 4456 KB Output is correct
4 Correct 541 ms 4436 KB Output is correct
5 Correct 623 ms 4368 KB Output is correct
6 Correct 625 ms 4364 KB Output is correct
7 Correct 663 ms 4556 KB Output is correct
8 Correct 397 ms 4448 KB Output is correct
9 Correct 54 ms 4436 KB Output is correct
10 Correct 843 ms 4388 KB Output is correct
11 Correct 836 ms 4436 KB Output is correct
12 Correct 874 ms 4520 KB Output is correct
13 Correct 870 ms 1152 KB Output is correct
14 Correct 536 ms 1108 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 763 ms 1144 KB Output is correct
2 Correct 40 ms 1248 KB Output is correct
3 Correct 367 ms 1312 KB Output is correct
4 Correct 39 ms 1152 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 300 ms 828 KB Output is correct
7 Correct 22 ms 932 KB Output is correct
8 Correct 37 ms 852 KB Output is correct
9 Correct 33 ms 852 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 14 ms 844 KB Output is correct

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 5 ms 844 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 824 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 26 ms 4184 KB Output is correct
8 Correct 25 ms 4180 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Execution timed out 2096 ms 224876 KB Time limit exceeded
13 Halted 0 ms 0 KB -