제출 #465618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465618		Rafi22	From Hacks to Snitches (BOI21_watchmen)	C++14	0 / 100	2757 ms	20100 KiB

watchmen

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=250007,K=1007;

vector<int>G[N];
vector<int>d[N];
int s[K];
vector<int>path[K];
int co[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,a,b,k;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    cin>>k;
    s[0]=1;
    for(int i=1;i<=k;i++)
    {
        cin>>s[i];
        path[i]=vector<int>(s[i]);
        for(int j=0;j<s[i];j++)
        {
            cin>>path[i][j];
            co[path[i][j]]=i;
            d[path[i][j]]=vector<int>(s[i],inf);
            d[path[i][j]][j]=-1;
        }
    }
    for(int i=1;i<=n;i++) if(!co[i]) d[i]=vector<int>(1,inf);
    priority_queue<pair<int,pair<int,int>>>Q;
    d[1][0]=0;
    Q.push({0,{1,0}});
    while(sz(Q)>0)
    {
        int v=Q.top().nd.st;
        int l=Q.top().nd.nd;
        int t=-Q.top().st;
       // cout<<v<<" "<<l<<" "<<t<<endl;
        Q.pop();
        if(t>d[v][l]) continue;
        for(auto u:G[v])
        {
            if(!co[u])
            {
                if(t+1<d[u][0])
                {
                    d[u][0]=t+1;
                    Q.push({-d[u][0],{u,0}});
                }
            }
            else
            {
                for(int i=0; i<s[co[u]]; i++)
                {
                    if(co[v])
                    {
                        if(co[u]!=co[v]) return 2137;
                        if(path[co[v]][l]==u&&path[co[v]][(l+1)%s[co[v]]]==v) continue;
                    }
                    int nt=t+1+(i-(t+1)%s[co[u]]+s[co[u]])%s[co[u]];
                    if(nt<d[u][i])
                    {
                        d[u][i]=nt;
                        Q.push({-d[u][i],{u,i}});
                    }
                }
            }
        }
        //Zostan w miejscu
        if(t+1<d[v][(l+1)%s[co[v]]])
        {
            d[v][(l+1)%s[co[v]]]=t+1;
            Q.push({-d[v][(l+1)%s[co[v]]],{v,(l+1)%s[co[v]]}});
        }
    }
    int ans=inf;
    for(auto x:d[n]) ans=min(ans,x);
    if(ans==inf) cout<<"impossible";
    else cout<<ans;
    return 0;
}

• 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