Submission #1204129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204129		Unforgettablepl	From Hacks to Snitches (BOI21_watchmen)	C++20	15 / 100	6053 ms	223444 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<vector<int>> adj(N+1);
    for(int i=1;i<=M;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    int K;
    cin >> K;
    vector<int> isPartOfWatchman(N+1);
    vector<int> idxInWalk(N+1);
    vector<int> lengthOfWalk(K+1);
    vector walk(K+1,vector<int>(1500));
    for(int i=1;i<=K;i++){
        int l;cin>>l;
        lengthOfWalk[i]=l;
        for(int j=0;j<l;j++){
            int x;
            cin >> x;
            idxInWalk[x]=j;
            isPartOfWatchman[x]=i;
            walk[i][j]=x;
        }
    }
    priority_queue<pair<int,int>> pq;
    set<pair<int,int>> visited;
    pq.emplace(0,1);
    while(!pq.empty()){
        auto [dist,idx] = pq.top();pq.pop();dist=-dist;
        if(isPartOfWatchman[idx]){
            int len = lengthOfWalk[isPartOfWatchman[idx]];
            if(visited.count({idx,dist%len}))continue;  
            visited.emplace(idx,dist%len);
        } else {
            if(visited.count({idx,0ll}))continue;
            visited.emplace(idx,0);
            if(idx==N){
                cout << dist << '\n';
                return 0;
            }
        }
        for(int&i:adj[idx]){
            if(isPartOfWatchman[i]){
                int whichWalk = isPartOfWatchman[i];
                int len = lengthOfWalk[whichWalk];
                int idxWalk = idxInWalk[i];
                int nextMeet = (idxWalk-(dist)%len + len)%len + dist + 1;
                if(!isPartOfWatchman[idx] and !visited.count({i,nextMeet%len})){
                    pq.emplace(-nextMeet,i);
                }
                if(walk[whichWalk][(dist+1)%len]==i){
                    continue;
                } else if(walk[whichWalk][(dist)%len]==i and !visited.count({i,(dist+1)%len})){
                    if(walk[whichWalk][(dist+1)%len]!=idx){
                        pq.emplace(-dist-1,i);
                    }
                } else if(!visited.count({i,(dist+1)%len})){
                    pq.emplace(-dist-1,i);
                }
            } else {
                if(!visited.count({i,dist+1}))
                    pq.emplace(-dist-1,i);
            }
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20