oj.uz

Submission #584122

# Submission time Handle Problem Language Result Execution time Memory
584122 2022-06-26T20:13:33 Z yanndev Toy Train (IOI17_train) C++17
27 / 100
 937 ms 2516 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX = 5042;
int dp[16][1 << 15];
bool canGo[MX];
bool goToMe[MX];
vector<int> graph[MX];
vector<int> rev[MX];

// 5 pts 2h37

void go(int node) {
    canGo[node] = true;
    for (auto& x: graph[node])
        if (!canGo[x])
            go(x);
}

void go2(int node, vector<int>& r) {
    canGo[node] = true;
    for (auto& x: graph[node])
        if (!canGo[x] && !r[x])
            go2(x, r);
}


void rgo(int node) {
    goToMe[node] = true;
    for (auto& x: rev[node])
        if (!goToMe[x])
            rgo(x);
}

int solve(int pos, int vis, vector<int>& a, vector<int>& r) {
    if (dp[pos][vis] != -1)
        return dp[pos][vis];

    if (vis & (1 << pos))
        return (dp[pos][vis] = r[pos]);

    if (a[pos]) {
        dp[pos][vis] = 0;
        for (auto& x: graph[pos]) {
            int nxtMsk = vis | (1 << pos);
            if (solve(x, nxtMsk, a, r) == 1)
                dp[pos][vis] = 1;
        }
    } else {
        dp[pos][vis] = 1;
        for (auto& x: graph[pos]) {
            int nxtMsk = vis | (1 << pos);
            if (solve(x, nxtMsk, a, r) == 0)
                dp[pos][vis] = 0;
        }
    }

    return dp[pos][vis];
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    int n;
    int myStations = 0;
    n = (int)a.size();

    for (int i = 0; i < MX; i++) {
        graph[i].clear();
        rev[i].clear();
    }

    vector<int> ans (n);
    bool isChain = true;

    for (int i = 0; i < (int)u.size(); i++) {
        graph[u[i]].push_back(v[i]);
        rev[v[i]].push_back(u[i]);
        if (!(u[i] == v[i] || v[i] == u[i] + 1))
            isChain = false;
    }

    for (int i = 0; i < n; i++)
        myStations += a[i];

    if (isChain) {
        for (int i = n - 1; i >= 0; i--) {
            bool hasSelf = false;
            bool hasNext = false;

            for (auto& x: graph[i]) {
                if (x == i) {
                    hasSelf = true;
                } else {
                    hasNext = true;
                }
            }

            if (a[i] == 1) {
                if (hasSelf && r[i])
                    ans[i] = 1;
                else if (hasNext)
                    ans[i] = ans[i + 1];
            } else {
                if (hasSelf && !r[i])
                    ans[i] = 0;
                else if (hasNext)
                    ans[i] = ans[i + 1];
                else
                    ans[i] = 1;
            }
        }
    } else if (myStations == 0) {
        for (auto& x: ans)
            x = 1;
        for (int i = 0; i < n; i++) {
            if (!r[i]) {
                memset(canGo, false, sizeof(canGo));
                memset(goToMe, false, sizeof(goToMe));

                for (auto& x: graph[i])
                    if (!r[x])
                        go2(x, r);
                for (auto& x: rev[i])
                    rgo(x);
                
                if (canGo[i]) {
                    for (int j = 0; j < n; j++)
                        if (goToMe[j])
                            ans[j] = 0;
                }
            }
        }
    } else if (myStations == n) {
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                memset(canGo, false, sizeof(canGo));
                memset(goToMe, false, sizeof(goToMe));

                for (auto& x: graph[i])
                    go(x);
                for (auto& x: rev[i])
                    rgo(x);
                
                if (canGo[i]) {
                    for (int j = 0; j < n; j++)
                        if (goToMe[j])
                            ans[j] = 1;
                }
            }
        }
    } else if (n <= 15) {
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                ans[i] = solve(i, 0, a, r);
            }
        }

        for (int i = 0; i < n; i++)
            ans[i] = solve(i, 0, a, r);
    }

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 1008 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1492 KB Output is correct
2 Correct 71 ms 1512 KB Output is correct
3 Correct 97 ms 1492 KB Output is correct
4 Correct 462 ms 1416 KB Output is correct
5 Correct 82 ms 1364 KB Output is correct
6 Correct 68 ms 1384 KB Output is correct
7 Correct 473 ms 1364 KB Output is correct
8 Correct 6 ms 1364 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 9 ms 1236 KB Output is correct
11 Correct 6 ms 1236 KB Output is correct
12 Correct 6 ms 1236 KB Output is correct
13 Correct 7 ms 1348 KB Output is correct
14 Correct 7 ms 1364 KB Output is correct
15 Correct 8 ms 1380 KB Output is correct
16 Correct 7 ms 1364 KB Output is correct
17 Correct 7 ms 1364 KB Output is correct
18 Correct 249 ms 1108 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1252 KB Output is correct
2 Correct 223 ms 1280 KB Output is correct
3 Correct 412 ms 1556 KB Output is correct
4 Correct 263 ms 1564 KB Output is correct
5 Correct 577 ms 1592 KB Output is correct
6 Correct 501 ms 1568 KB Output is correct
7 Correct 512 ms 1548 KB Output is correct
8 Correct 335 ms 1520 KB Output is correct
9 Correct 7 ms 1420 KB Output is correct
10 Correct 201 ms 1636 KB Output is correct
11 Correct 82 ms 1648 KB Output is correct
12 Correct 214 ms 1636 KB Output is correct
13 Correct 937 ms 1624 KB Output is correct
14 Correct 522 ms 1632 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 1008 KB Output is correct
12 Incorrect 2 ms 2516 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -