제출 #1188514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188514		DanielPr8	From Hacks to Snitches (BOI21_watchmen)	C++20	0 / 100	9 ms	2368 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()
priority_queue<pair<ll,pll>, vector<pair<ll,pll>>, greater<pair<ll,pll>>> pq;
vvl ds;
void pp(pair<ll,pll> a){
    if(a.s.f==-1){
        if(ds[a.s.s][0]>a.f){
            pq.push(a);
            ds[a.s.s][0]=a.f;
        }
    }
    else{
        if(ds[a.s.s][a.s.f]>a.f){
            pq.push(a);
            ds[a.s.s][a.s.f]=a.f;
        }
    }
}
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);
    }
    ds = vvl(n, vll(1, 1e11));
    cin >> k;
    vvl rou(k+1);
    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);
            rou[i].pb(a);
        }
    }
    pp({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){
                    pp({t+1, {-1, i}});
                }
                else{
                    if((t+1)%ln[i]!=id[i])pp({t+1, {(t+1)%ln[i], i}});
                    pp({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){
                    pp({t+1, {-1, i}});
                }
                else if(ma[i]!=ma[cr]){
                    if((t+1)%ln[i]!=id[i])pp({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;
                    pp({t+1, {(t+1)%ln[i], i}});
                }
            }
            g[cr].clear();
            g[cr].pb(cr);
            g[cr].pb(rou[ma[cr]][(id[cr]+1)%ln[cr]]);
            g[cr].pb(rou[ma[cr]][(id[cr]-1)%ln[cr]]);
        }
    }
    ll ans = 1e11;
    for(ll i:ds[n-1])ans = min(ans, i);
    if(ans!=1e11)cout << ans;
    else cout << "impossible";
}

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