Submission #729061

#	Time	Username	Problem	Language	Result	Execution time	Memory
729061		Jean7	From Hacks to Snitches (BOI21_watchmen)	C++14	5 / 100	1199 ms	130540 KiB

watchmen

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pob pop_back
#define pub push_back
#define lb lower_bound
#define ub upper_bound
#define low (i&(-i))
#define le (node<<1)
#define ri (node<<11)
#define mid ((l+r)>>1)
#define no void(cout<<"NO\n")
#define zer void(cout<<"0\n")
#define one void(cout<<"-1\n")
#define yes void(cout<<"YES\n")
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define mm(x,y) memset(x,y,sizeof(x))

using namespace std ;

const int L = 23 ;
const int B = 750 ;
const int T = 1e3+3 ;
const int N = 1e6+6 ;
const int M = 1e9+7 ;
const int D = 998244353 ;
const long long O = 4557430888798830399 ;

vector <int> g[N] ;
int n , m , k , a[127] , dis[100005][127] ;

int bfs () {
    mm(dis,O) ;
    queue <pair<int,int>> q ;
    q.push({1,0}) ;
    dis[1][0] = 0 ;
    while ( !q.empty() ) {
        int x = q.front().ff ;
        if ( x == n ) {
            return *min_element ( dis[n] , dis[n] + 127 ) ;
        }
        int id = q.front().ss ;
        int idn = (id+1)%k ;
        q.pop() ;
        for ( auto it : g[x] ) {
            if ( it == a[idn] ) {
                continue ;
            }
            if ( it == a[id] && x == a[idn] ) {
                continue ;
            }
            if ( dis[it][idn] <= dis[x][id] + 1 ) {
                continue ;
            }
            dis[it][idn] = dis[x][id] + 1 ;
            q.push({it,idn}) ;
        }
    }
    return O ;
}

inline void solve () {
    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; i++ ) {
        g[i].pub(i) ;
    }
    while ( m-- ) {
        int x , y ;
        cin >> x >> y ;
        g[x].pub(y) ;
        g[y].pub(x) ;
    }
    cin >> k >> k ;
    for ( int i = 0 ; i < k ; i++ ) {
        cin >> a[i] ;
    }
    int ans = bfs () ;
    if ( ans == O ) {
        cout << "impossible" ;
    }
    else {
        cout << ans ;
    }
}

signed main () {
    //freopen ( ".in" , "r" , stdin ) ;
    //freopen ( ".out" , "w" , stdout ) ;
    cin.tie(0) ;
    cout.tie(0) ;
    ios_base::sync_with_stdio(0) ;
    //cout << setprecision(14) << fixed ;
    int tc = 1 ;
    //cin >> tc ;
    while ( tc-- ) {
        solve() ;
    }
    return 0 ;
}

///  JJJJJJJ EEEEEEE  AAAAA  NN   NN 7777777
///     JJ   EE      AA   AA NNN  NN     77
///     JJ   EEEEEE  AAAAAAA NN N NN    77
///  JJ JJ   EE      AA   AA NN  NNN   77
///  JJJJJ   EEEEEEE AA   AA NN   NN  77

Compilation message (stderr)

watchmen.cpp: In function 'long long int bfs()':
watchmen.cpp:35:12: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   35 |     mm(dis,O) ;
      |            ^
watchmen.cpp:19:26: note: in definition of macro 'mm'
   19 | #define mm(x,y) memset(x,y,sizeof(x))
      |                          ^

• Subtask 1: 5 / 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