oj.uz

Submission #729061

# Submission time Handle Problem Language Result Execution time Memory
729061 2023-04-23T13:01:18 Z Jean7 From Hacks to Snitches (BOI21_watchmen) C++14
5 / 100
 1199 ms 130540 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125512 KB Output is correct
2 Correct 522 ms 130020 KB Output is correct
3 Correct 730 ms 130148 KB Output is correct
4 Correct 1111 ms 130540 KB Output is correct
5 Correct 49 ms 123176 KB Output is correct
6 Correct 859 ms 130236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 125608 KB Output is correct
2 Correct 494 ms 129944 KB Output is correct
3 Correct 747 ms 130100 KB Output is correct
4 Correct 1199 ms 130540 KB Output is correct
5 Correct 53 ms 123212 KB Output is correct
6 Correct 979 ms 130196 KB Output is correct
7 Incorrect 341 ms 129968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 125608 KB Output is correct
2 Correct 494 ms 129944 KB Output is correct
3 Correct 747 ms 130100 KB Output is correct
4 Correct 1199 ms 130540 KB Output is correct
5 Correct 53 ms 123212 KB Output is correct
6 Correct 979 ms 130196 KB Output is correct
7 Incorrect 341 ms 129968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 125608 KB Output is correct
2 Correct 494 ms 129944 KB Output is correct
3 Correct 747 ms 130100 KB Output is correct
4 Correct 1199 ms 130540 KB Output is correct
5 Correct 53 ms 123212 KB Output is correct
6 Correct 979 ms 130196 KB Output is correct
7 Incorrect 341 ms 129968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125512 KB Output is correct
2 Correct 522 ms 130020 KB Output is correct
3 Correct 730 ms 130148 KB Output is correct
4 Correct 1111 ms 130540 KB Output is correct
5 Correct 49 ms 123176 KB Output is correct
6 Correct 859 ms 130236 KB Output is correct
7 Correct 80 ms 125608 KB Output is correct
8 Correct 494 ms 129944 KB Output is correct
9 Correct 747 ms 130100 KB Output is correct
10 Correct 1199 ms 130540 KB Output is correct
11 Correct 53 ms 123212 KB Output is correct
12 Correct 979 ms 130196 KB Output is correct
13 Incorrect 341 ms 129968 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125512 KB Output is correct
2 Correct 522 ms 130020 KB Output is correct
3 Correct 730 ms 130148 KB Output is correct
4 Correct 1111 ms 130540 KB Output is correct
5 Correct 49 ms 123176 KB Output is correct
6 Correct 859 ms 130236 KB Output is correct
7 Correct 80 ms 125608 KB Output is correct
8 Correct 494 ms 129944 KB Output is correct
9 Correct 747 ms 130100 KB Output is correct
10 Correct 1199 ms 130540 KB Output is correct
11 Correct 53 ms 123212 KB Output is correct
12 Correct 979 ms 130196 KB Output is correct
13 Incorrect 341 ms 129968 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125512 KB Output is correct
2 Correct 522 ms 130020 KB Output is correct
3 Correct 730 ms 130148 KB Output is correct
4 Correct 1111 ms 130540 KB Output is correct
5 Correct 49 ms 123176 KB Output is correct
6 Correct 859 ms 130236 KB Output is correct
7 Correct 80 ms 125608 KB Output is correct
8 Correct 494 ms 129944 KB Output is correct
9 Correct 747 ms 130100 KB Output is correct
10 Correct 1199 ms 130540 KB Output is correct
11 Correct 53 ms 123212 KB Output is correct
12 Correct 979 ms 130196 KB Output is correct
13 Incorrect 341 ms 129968 KB Output isn't correct
14 Halted 0 ms 0 KB -