oj.uz

Submission #748081

# Submission time Handle Problem Language Result Execution time Memory
748081 2023-05-25T11:44:20 Z vjudge1 From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 6000 ms 16592 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6056 ms 16552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6071 ms 16592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6071 ms 16592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6071 ms 16592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6056 ms 16552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6056 ms 16552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13012 KB Output is correct
2 Execution timed out 6056 ms 16552 KB Time limit exceeded
3 Halted 0 ms 0 KB -