Областная олимпиада по информатике, 2009-2010 учебный год

Задача B. Путешествие

Ограничение по времени:

2 sec.

Ограничение по памяти:

64MB

Ваш друг решил отправиться в путешествие по городам страны, которых всего N. Проезд по каждой дороге занимает ровно один день. Каждый день он будет переезжать из города в город (он может возвращаться в город, в котором уже был). Определите, в каких городах он может оказаться через К дней после начала путешествия, если в первый день он выезжает из города 1.

Формат входного файла

Первая строка входного файла содержит три целых числа N, M и K (2 ≤ N ≤ 20, 1 ≤ M ≤ N (N – 1) / 2, 1 ≤ K ≤$10^9$). Следующие М строк содержат описание дорог в виде двух целых чисел – номеров городов, между которыми проходит соответствующая дорога. Города нумеруются целыми числами от 1 до N. Числа в строках разделены пробелами.

Формат выходного файла

В выходной файл выведите через пробел номера городов, в которых может оказаться ваш друг через К дней. Все числа должны быть различными.

Примеры:

Вход:

7 6 3
1 2
3 2
3 4 
1 5 
5 6
7 6

 Ответ:

2 5 4 7

Вход:

3 2 1 
2 1
2 3

 Ответ:

2

Комментарий/решение

verdict :AC //// govno code

показать/скрыть код

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define ld long double
#define lb lower_bound
#define ub upper_bound
#define mem(a) memset((a), (0), sizeof((a))

#define ar array
#define ll long long
#define ull unsigned long long
#define lala ios_base::sync_with_stdio(0);
#define FOR(l,r,c) for(int c=(l);c<=(r);c++)

#define open(name) \
freopen(name".in", "r", stdin); \
freopen (name".out", "w", stdout);

const int N = 2e5 + 7;
const int INF = 2e9 + 7;
const int MOD = 1e9 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m;
int k, t = 0;
vector <int> g[N], d(N, -1);
set <int> ans;
int used[27][27];

void del() {
    FOR(1, n, i) {
        FOR(1, n, j) {
            used[i][j] = 0;
        }
    }
}
void dfs(int v, int flag) {
    if (flag) {
        d[v] = flag;
        ans.insert(v);
    }
    for (int to : g[v]) {
        if (!used[v][to]) {
            used[v][to] = 1;
            if (flag == 1) {
                dfs(to, 0);
            } else {
                dfs(to, 1);
            }
        }
    }
}

void solve() {
    cin >> n >> m >> k;
    del();
    for (int i = 1, l, r; i <= m; i ++) {
        cin >> l >> r;
        g[l].PB(r);
        g[r].PB(l);
    }
    int flag = 0;
    if (k % 2 == 0) flag ++;
    if (flag) {
        d[1] = 1;
        for (int i = 0; i < g[1].size(); i ++) {
            int to = g[1][i];
            for (int j = 0; j < g[to].size(); j ++) {
                int to1 = g[to][j];
                d[to1] = 1;
                dfs(to1, 1);
                ans.insert(to1);
                del();
                for (int j = 0; j < g[to1].size(); j ++) {
                    int to2 = g[to1][j];
                    for (int t = 0; t < g[to2].size(); t ++) {
                        int to3 = g[to2][t];
                        d[to3] = 1;
                        dfs(to3, 1);
                        ans.insert(to3);
                        del();
                    }
                }
            }
        }
        for (int i = 2; i <= n; i ++) {
            if (d[i] == 1) {
                dfs(i, 1);
                del();
            }
        }
    } else {
        d[1] = 0;
        for (int i = 0; i < g[1].size(); i ++) {
            int to = g[1][i];
            d[to] = 1;
            dfs(to, 1);
            ans.insert(to);
            del();
        }
        for (int i = 2; i <= n; i ++) {
            if (d[i] == 1) {
                dfs(i, 1);
                del();
            }

        }
    }

    for (int it : ans) cout << it << ' ';
    
}
main(){
    lala;
    open("B");
    solve();
}