oj.uz

Submission #237561

# Submission time Handle Problem Language Result Execution time Memory
237561 2020-06-07T10:23:28 Z VEGAnn Planinarenje (COCI18_planinarenje) C++14
64 / 160
 252 ms 262148 KB 
#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 = 5010;
const int PW = (1 << 20);
vector<int> g[NN];
int n, m, net[N], f[PW][N], rt, 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 (rt = 0; rt < n; rt++) {
        dfs(rt, -1);

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

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 82540 KB Output is correct
2 Correct 221 ms 82556 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 82680 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 191 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -