Submission #446905

#	Time	Username	Problem	Language	Result	Execution time	Memory
446905		wiwiho	From Hacks to Snitches (BOI21_watchmen)	C++14	50 / 100	6098 ms	163100 KiB

watchmen

#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))

using namespace std;

typedef long long ll;
const ll MAX = 1LL << 60;

using pii = pair<int, int>;

ll iceil(ll a, ll b){
    return (a + b - 1) / b;
}

int n, m, k;
vector<int> len;
vector<int> rid; // route id
vector<int> id; // id in route
vector<vector<int>> g, tg, rg;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    rid.resize(n + 1);
    id.resize(n + 1);
    g.resize(n + 1);
    tg.resize(n + 1);
    rg.resize(n + 1);
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    vector<vector<ll>> dis(n + 1, vector<ll>(1, MAX));

    cin >> k;
    len.resize(k + 1);
    len[0] = 1;
    for(int i = 1; i <= k; i++){
        cin >> len[i];
        for(int j = 0; j < len[i]; j++){
            int v;
            cin >> v;
            rid[v] = i;
            id[v] = j;
            dis[v].resize(len[i], MAX);
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j : g[i]){
            if(rid[j] == 0) tg[i].eb(j);
            else rg[i].eb(j);
        }
    }

    dis[1][0] = 0;
    priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<>> pq;
    pq.push(mp(0, mp(1, 0)));
    vector<bool> vst(n + 1);
    while(!pq.empty()){
        ll d = pq.top().F;
        int now = pq.top().S.F;
        int t = pq.top().S.S;
        pq.pop();
        if(d != dis[now][t]) continue;
        if(!vst[now]){
            for(int i : tg[now]){
                if(d + 1 < dis[i][0]){ dis[i][0] = d + 1;
                    pq.push(mp(d + 1, mp(i, 0)));
                }
            }
        }
        vst[now] = true;


        // stay
        if(rid[now] != 0 && (t + 1) % len[rid[now]] != id[now]){
            int tmp = (t + 1) % len[rid[now]];
            if(d + 1 < dis[now][tmp]){
                dis[now][tmp] = d + 1;
                pq.push(mp(d + 1, mp(now, tmp)));
            }
        }

        // move
        for(int i : rg[now]){
            if(rid[now] == 0){
                int to = (d + 1) % len[rid[i]];
                if(to != id[i]){
                    if(d + 1 < dis[i][to]){
                        dis[i][to] = d + 1;
                        pq.push(mp(d + 1, mp(i, to)));
                    }
                }
                to = (id[i] + 1) % len[rid[i]];
                ll nd = ((d + 1) / len[rid[i]]) * len[rid[i]] + to;
                if(nd < d + 1) nd += len[rid[i]];
                if(nd < dis[i][to]){
                    dis[i][to] = nd;
                    pq.push(mp(nd, mp(i, to)));
                }
            }
            else if(rid[now] == rid[i]){
                int to = (d + 1) % len[rid[i]];
                if(to == id[i]) continue;
                if(to == id[now] && t == id[i]) continue;
                if(d + 1 < dis[i][to]){
                    dis[i][to] = d + 1;
                    pq.push(mp(d + 1, mp(i, to)));
                }
            }
            else{
                for(int r = 0; r < len[rid[i]]; r++){
                    ll nd = d + (ll) r * len[rid[now]];
                    int to = (nd + 1) % len[rid[i]];
                    if(to == id[i]) continue;
                    if(nd + 1 < dis[i][to]){
                        dis[i][to] = nd + 1;
                        pq.push(mp(nd + 1, mp(i, to)));
                    }
                }
            }
        }
    }

    if(dis[n][0] != MAX) cout << dis[n][0] << "\n";
    else cout << "impossible\n";

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20