Submission #584106

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584106	2022-06-26T19:41:20 Z	yanndev	Toy Train (IOI17_train)	C++17	Compilation error	0 ms	0 KB

train

#include <bits/stdc++.h>
using namespace std;

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

// 5 pts 2h37

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;
    n = (int)a.size();

    for (int i = 0; i < MX; i++)
        graph[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]);
        if (!(u[i] == v[i] || v[i] == u[i] + 1))
            isChain = false;
    }

    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 (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;
}

Compilation message

train.cpp: In function 'int solve(int, int, std::vector<int>&, std::vector<int>&)':
train.cpp:14:27: error: expected ';' before 'return'
   14 |     if ((vis & (1 << pos))
      |                           ^
      |                           ;
   15 |         return (dp[pos][vis] = r[pos]);
      |         ~~~~~~             
train.cpp:17:5: error: expected primary-expression before 'if'
   17 |     if (a[pos]) {
      |     ^~
train.cpp:15:40: error: expected ')' before 'if'
   15 |         return (dp[pos][vis] = r[pos]);
      |                                        ^
      |                                        )
   16 | 
   17 |     if (a[pos]) {
      |     ~~                                  
train.cpp:14:8: note: to match this '('
   14 |     if ((vis & (1 << pos))
      |        ^
train.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^