제출 #748081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748081		vjudge1	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	6071 ms	16592 KiB

watchmen

#include<bits/stdc++.h>
using namespace std;
const int maxn=250000+10;
vector<int>adj[maxn],allk[maxn];
int n,m,k,nowk[maxn],dp[2][maxn],now=1,vis[maxn],nexta[maxn];

int bad(int i){
    int ret=nowk[i]+1;
    int sz=allk[i].size();
    if(ret>=sz){
        ret=0;
    }
    return ret;
}

void upd(int ind){
    now^=1;
    for(int i=1;i<=n;i++){
        if(vis[i]==ind){
            dp[now][i]=0;
            continue;
        }
        if(dp[now^1][i]==1)
        {
            dp[now][i]=1;
            continue;
        }
        int f=0;
        for(auto x:adj[i]){
            if(dp[now^1][x]==1){
                if(vis[i]!=ind-1){
                    f=1;
                    break;
                }   
                if(nexta[i]!=x){
                    f=1;
                    break;
                }
            }
        }
        if(f){
            dp[now][i]=1;
        }
        else{
            dp[now][i]=0;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int ki;
        cin>>ki;
        allk[i].resize(ki);
        for(int j=0;j<ki;j++){
            cin>>allk[i][j];
        }
    }
    for(int i=0;i<=n;i++){
        vis[i]=-1;
    }
    for(int i=1;i<=k;i++){
        vis[allk[i][0]]=0;
    }
    dp[1][1]=1;
    int res=-1;
    for(int i=1;i<=k+n+2;i++){
        for(int j=1;j<=k;j++){
            nexta[allk[j][nowk[j]]]=allk[j][bad(j)];
            nowk[j]=bad(j);
            vis[allk[j][nowk[j]]]=i;
        //  cout<<nowk[j]<<" "<<allk[j][nowk[j]]<<"\n";
        }
        upd(i);
    //  for(int j=1;j<=n;j++){
    ///     cout<<i<<" "<<j<<" "<<dp[now][j]<<"\n";
    //  }
        if(dp[now][n]==1){
            res=i;
            break;
        }
    }
    if(res==-1){
        cout<<"impossible\n";
    }
    else{
        cout<<res<<"\n";
    }
}

• 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