oj.uz

Submission #935738

# Submission time Handle Problem Language Result Execution time Memory
935738 2024-02-29T13:02:07 Z berr From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 240 ms 524292 KB 
//#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

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

# Verdict Execution time Memory Grader output
1 Correct 40 ms 19024 KB Output is correct
2 Runtime error 238 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19032 KB Output is correct
2 Runtime error 240 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19032 KB Output is correct
2 Runtime error 240 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19032 KB Output is correct
2 Runtime error 240 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 19024 KB Output is correct
2 Runtime error 238 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 19024 KB Output is correct
2 Runtime error 238 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 19024 KB Output is correct
2 Runtime error 238 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -