제출 #1284902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284902		swusjask	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	2 ms	592 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vpl = vector<pll>;

#define pb push_back
#define fi first
#define se second
#define f(i, a, b) for (ll i = a; i <= b; i++)
#define fr(i, a, b) for (ll i = b; i >= a; i--)
#define sz(x) (ll) x.size()
#define debug(val) cerr << #val << " = " << val << '\n';
#define all(x) x.begin(), x.end()

const ll MOD = 1e9 + 7;

void bfs(ll start, vector<vl> &adj, vector<pll> &path) {
    path[start] = {-1,1};
    queue<ll> q;
    q.push(start);

    while (!q.empty()) {
        ll u = q.front(); q.pop();
        ll ct = path[u].se;
        for (ll v: adj[u]) {
            if (path[v] != pll{-1,-1}) continue;
            path[v] = {u,ct+1};
            q.push(v);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // string name = "time";
    // freopen((name + ".in").c_str(), "r", stdin);
    // freopen((name + ".out").c_str(), "w", stdout);

    // precompute
    // vl dices = {1,2,3,4,5,6};

    ll n,m;
    cin >> n >> m;

    vector<vl> adj(n+1);
    vector<pll> path(n+1, pll({-1,-1}));

    f(i,1,m) {
        ll a,b;
        cin >> a >> b;
        adj[a].push_back(b),adj[b].push_back(a);
    }

    bfs(1,adj,path);

    ll len = path[n].se;
    if (len == -1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    // backtrack
    vl path2(len);
    ll i = len-1, u = n;
    path2[i--] = n;
    do {
        u = path[u].fi;
        path2[i--] = u;
    } while (u != 1);

    cout << len << "\n";

    f(i,0,len-1) cout << path2[i] << " \n"[i==len-1];
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70