Submission #237564

#	Time	Username	Problem	Language	Result	Execution time	Memory
237564		VEGAnn	Planinarenje (COCI18_planinarenje)	C++14	80 / 160	217 ms	262148 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 NN = 10010;
const int PW = (1 << 20);
vector<int> g[NN];
int n, m, net[N];
bool f[PW][N], ans[NN];

void dfs(int v, int p){
    if (v < n)
        ans[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);

        if (v < n){
            if (ans[u] == 0)
                ans[v] = 0;
        } else {
            if (ans[u] == 1)
                ans[v] = 1;
        }
    }
}

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

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

    cin >> n >> m;

    if (n < 11) {

        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 = 0; i < 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 = n; i < n + 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;
    }

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

        g[x].PB(y);
        g[y].PB(x);
    }

    for (int rt = 0; rt < n; rt++) {
        dfs(rt, -1);

        cout << (ans[rt] ? "Mirko\n" : "Slavko\n");
    }

    return 0;
}

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