oj.uz

답안 #237559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237559 2020-06-07T10:17:35 Z VEGAnn Planinarenje (COCI18_planinarenje) C++14
48 / 160
 246 ms 82424 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 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 = 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;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 82360 KB Output is correct
2 Correct 214 ms 82424 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 82424 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -