Submission #237558

#	Time	Username	Problem	Language	Result	Execution time	Memory
237558		VEGAnn	Planinarenje (COCI18_planinarenje)	C++14	0 / 160	280 ms	82552 KiB

planinarenje

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 20;
const int PW = (1 << 20);
vector<int> g[N];
int n, m, net[N], f[PW][N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        net[x] |= (1 << (y + n));
        net[y + n] |= (1 << x);
    }

    for (int msk = (1 << (n + n)) - 1; msk > 0; msk--)
    for (int lst = 0; lst < n + n; lst++)
        if (msk & (1 << lst)){
            if ((net[lst] | msk) == msk){
                if (lst < n)
                    f[msk][lst] = 1;
                else f[msk][lst] = 0;
            } else {
                if (lst < n){
                    for (int i = n; i < n + n; i++)
                        if ((net[lst] & (1 << i)) && !(msk & (1 << i))){
                            int nmsk = (msk | (1 << i));

                            if (f[nmsk][i] == 1){
                                f[msk][lst] = 1;
                                break;
                            }
                        }
                } else {
                    f[msk][lst] = 1;

                    for (int i = 0; i < n; i++)
                        if ((net[lst] & (1 << i)) && !(msk & (1 << i))){
                            int nmsk = (msk | (1 << i));

                            if (f[nmsk][i] == 0){
                                f[msk][lst] = 0;
                                break;
                            }
                        }
                }
            }
        }

    for (int i = 0; i < n; i++)
        cout << (f[(1 << i)][i] ? "Mirko\n" : "Slavko\n");

    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16