oj.uz

Submission #935742

# Submission time Handle Problem Language Result Execution time Memory
935742 2024-02-29T13:18:11 Z berr From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1218 ms 524288 KB 
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
  
const int N =250037;

int d[N][400];
bool vis[N][400];
bool vis2[N][400];

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(n);

        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] =vis2[v][tim]= 1;
            int next = (tim+1)%400;
            if(l+1<N){
                if(va[v]!=next){
                    if(d[v][next] > val+1||vis2[v][next]==0){
                        vis2[v][next] = 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||vis2[i][next]==0){
                            vis2[i][next] = 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||vis2[i][next]==0){
                            vis2[i][next]=1;
                            d[i][next]=val+1;
                            pq[l+1].push_back({i, next});
                        }
                    }
                }
            }
        }
        l++;
    }
    int ans = 1e9;

    for(int i=0; i<400; i++) if(vis[n-1][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:57: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]
   57 |         while(j<pq[l].size()){
      |               ~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 18004 KB Output is correct
2 Runtime error 1218 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 140 ms 17492 KB Output is correct
2 Runtime error 1166 ms 524288 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 140 ms 17492 KB Output is correct
2 Runtime error 1166 ms 524288 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 140 ms 17492 KB Output is correct
2 Runtime error 1166 ms 524288 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 144 ms 18004 KB Output is correct
2 Runtime error 1218 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 144 ms 18004 KB Output is correct
2 Runtime error 1218 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 144 ms 18004 KB Output is correct
2 Runtime error 1218 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -