oj.uz

Submission #584119

# Submission time Handle Problem Language Result Execution time Memory
584119 2022-06-26T20:01:41 Z yanndev Toy Train (IOI17_train) C++17
16 / 100
 501 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 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 == 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 3 ms 980 KB Output is correct
2 Correct 4 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 5 ms 980 KB Output is correct
7 Correct 3 ms 1064 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 5 ms 980 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 3 ms 980 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 40 ms 1516 KB Output is correct
2 Correct 72 ms 1492 KB Output is correct
3 Correct 118 ms 1492 KB Output is correct
4 Correct 462 ms 1440 KB Output is correct
5 Correct 80 ms 1492 KB Output is correct
6 Correct 66 ms 1576 KB Output is correct
7 Correct 501 ms 1564 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 9 ms 1492 KB Output is correct
10 Correct 12 ms 1456 KB Output is correct
11 Correct 7 ms 1492 KB Output is correct
12 Correct 7 ms 1492 KB Output is correct
13 Correct 8 ms 1588 KB Output is correct
14 Correct 11 ms 1592 KB Output is correct
15 Correct 7 ms 1620 KB Output is correct
16 Correct 8 ms 1716 KB Output is correct
17 Correct 7 ms 1584 KB Output is correct
18 Correct 251 ms 1288 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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