Submission #1188434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188434		DanielPr8	From Hacks to Snitches (BOI21_watchmen)	C++20	15 / 100	6097 ms	304112 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, m, a, b, l, k;
    cin >> n >> m;
    vvl g(n);
    vll ln(n), id(n), ma(n);
    for(ll i = 0; i < m; ++i){
        cin >> a >> b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    vvl ds(n, vll(1, 1e11));
    cin >> k;
    for(ll i = 1; i <= k; ++i){
        cin >> l;
        for(ll j = 0; j < l; ++j){
            cin >> a;a--;
            ln[a]=l;
            id[a]=j;
            ma[a]=i;
            ds[a]=vll(l, 1e11);
            g[a].pb(a);
        }
    }
    priority_queue<pair<ll,pll>, vector<pair<ll,pll>>, greater<pair<ll,pll>>> pq;
    pq.push({0, {-1,0}});

    while(!pq.empty()){
        auto [t, e] = pq.top();
        pq.pop();
        auto [r, cr] = e;
        if(r==-1){
            if(t>=ds[cr][0])continue;
            ds[cr][0]=t;
            for(ll i:g[cr]){
                if(ma[i]==0){
                    pq.push({t+1, {-1, i}});
                }
                else{
                    if((t+1)%ln[i]!=id[i])pq.push({t+1, {(t+1)%ln[i], i}});
                    pq.push({t+1+((id[i]-t)%ln[i]+ln[i])%ln[i], {(id[i]+1)%ln[i], i}});
                }
            }
        }
        else{
            if(t>=ds[cr][r])continue;
            ds[cr][r]=t;
            for(ll i:g[cr]){
                if(ma[i]==0){
                    pq.push({t+1, {-1, i}});
                }
                else if(ma[i]!=ma[cr]){
                    if((t+1)%ln[i]!=id[i])pq.push({t+1, {(t+1)%ln[i], i}});
                }
                else{
                    if((t+1)%ln[i]==id[i])continue;
                    if(t%ln[i]==id[i] && (t+1)%ln[cr]==id[cr])continue;
                    pq.push({t+1, {(t+1)%ln[i], i}});
                }
            }
        }
    }
    ll ans = 1e11;
    for(ll i:ds[n-1])ans = min(ans, i);
    if(ans!=1e11)cout << ans;
    else cout << "impossible";
}

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