제출 #1289703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289703		ctfox	Norela (info1cup18_norela)	C++17	0 / 100	1094 ms	8896 KiB

norela

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

int n, m;
vector<int> spell_masks;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    spell_masks.resize(m);

    for (int i = 0; i < m; ++i) {
        int q;
        cin >> q;
        int mask = 0;
        for (int j = 0; j < q; ++j) {
            int a;
            cin >> a;
            mask |= (1 << (a - 1));
        }
        spell_masks[i] = mask;
    }

    int goal = (1 << n) - 1;
    queue<int> q;
    map<int, vector<int>> visited;

    q.push(0);
    visited[0] = {};

    while (!q.empty()) {
        int state = q.front();
        q.pop();
        vector<int> path = visited[state];

        if (state == goal) {
            cout << path.size() << "\n";
            for (int idx : path) cout << idx << " ";
            cout << "\n";
            return 0;
        }

        for (int i = 0; i < m; ++i) {
            int new_state = state ^ spell_masks[i];
            vector<int> new_path = path;
            new_path.push_back(i + 1);

            if (!visited.count(new_state) || visited[new_state] > new_path) {
                visited[new_state] = new_path;
                q.push(new_state);
            }
        }
    }

    cout << -1 << "\n"; // Çözüm yoksa
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25