Submission #935738

#	Time	Username	Problem	Language	Result	Execution time	Memory
935738		berr	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	240 ms	524292 KiB

watchmen

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
  
const int N =250037;
int d[N][1501];
bool vis[N][1501];
vector<int> g[N];
vector<array<int, 2>> pq[N];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m; cin >> n >> m;

    vector<int> va(n, -1);
    vector<int> nxt(n);
    
    for(int i=0; i<n; i++){
        for(int l=0; l<1501; l++){
            d[i][l]=1e9;
        }
    }

    for(int i=0; i<m; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    int k; cin >> k;
    int ma = 0;

    for(int i=0; i<k; i++){
        int siz; cin >> siz;
        ma = max(ma, siz);
        vector<int> a(siz);
        for(auto &i: a) cin >> i, i--;

        for(int i=0; i<siz; i++){
        
            va[a[i]] = i;
            if(i!=siz-1) nxt[a[i]] =a[i+1];
            else nxt[a[i]]=a[0];
        }
    }
    d[0][0] = 0;

    pq[0].push_back({0, 0});
    int l=0;
    while(l<N){
        int j=0;
        while(j<pq[l].size()){
            auto [ v, tim] = pq[l][j];
            j++;
            int val = l;
            //cout<<v<<" "<<tim<<" "<<val<<"\n";

            if(vis[v][tim]) continue;
           
            vis[v][tim] = 1;
            int next = (tim+1)%ma;
            if(l+1<N){
                if(va[v]!=next){
                    if(d[v][next] > val+1){
                        d[v][next]=val+1;

                        pq[l+1].push_back({v, next});
                    }
                } 

                for(auto i: g[v]){ 
                    if(va[i]!=tim&&va[i]!=next){
                        if(d[i][next]>val+1){
                            d[i][next]=val+1;
                            pq[l+1].push_back({i, next});
                        }
                    }
                    else if(va[i]==tim && nxt[i]!=v){
                        if(d[i][next]>val+1){
                            d[i][next]=val+1;
                            pq[l+1].push_back({i, next});
                        }
                    }
                }
            }
        }
        l++;
    }
    int ans = 1e9;

    for(int i=0; i<=1500; i++) ans=min(ans, d[n-1][i]);
    if(ans==1e9) cout<<"impossible"<<"\n";
    else cout<<ans<<"\n";
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(j<pq[l].size()){
      |               ~^~~~~~~~~~~~~

• 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