Submission #1240816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240816		KindaGoodGames	From Hacks to Snitches (BOI21_watchmen)	C++20	5 / 100	1085 ms	55368 KiB

watchmen

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
#define tiii tuple<int,int,int>

int INF = 1e9;

int main(){
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n);

    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int k;
    cin >> k;
    vector<vector<int>> watchmen(k);
    vector<int> len(k);

    int ma = 0;
    int leastcm = 1;
    
    for(int i = 0; i < k; i++){
        int l;
        cin >> l;
        len[i] = l;
        watchmen[i].resize(l);
        ma = max(ma,l);

        leastcm = lcm(leastcm, l);

        for(int j = 0; j < l; j++){
            cin >> watchmen[i][j];
            watchmen[i][j]--;
        }
    }

    queue<pii> q;
    vector<vector<int>> dist(ma, vector<int>(n, INF));

    q.push({0,0});

    while(q.size()){
        int d,v;

        tie(d,v) = q.front(); q.pop();

        bool valid = true;
        for(int i = 0; i < k; i++){
            if(watchmen[i][d%len[i]] == v) {
                valid = false;
                break;
            }
        }
        if(!valid || dist[d%leastcm][v] <= d) continue;
        dist[d%leastcm][v] = d;

        q.push({d+1,v});
        for(auto u : adj[v]){ 
            bool valid2 = true;
            for(int i = 0; i < k; i++){
                if(watchmen[i][d%len[i]] == u && watchmen[i][(d+1)%len[i]] == v) {
                    valid2 = false;
                    break;
                }
            }
            if(!valid2){
                continue;
            }
            q.push({d+1, u});
        }
    }

    int mi = INF;
    for(int i = 0; i < leastcm; i++){
        mi = min(mi, dist[i][n-1]);
    }

    if(mi == 1e9){
        cout << "impossible" << endl;
        return 0;
    }
    cout << mi << endl;
}

• 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