제출 #1229552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229552		LaMatematica14	From Hacks to Snitches (BOI21_watchmen)	C++20	0 / 100	436 ms	40240 KiB

watchmen

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

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>> adj(N+1);
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int K; cin >> K;
    vector<int> mod(K, -1), rem(N+1, -1), wat(N+1, -1);
    for (int i = 0; i < K; i++) {
        int l; cin >> l; mod[i] = l;
        for (int j = 0; j < l; j++) {
            int a; cin >> a;
            wat[a] = i;
            rem[a] = j;
        }
    }
    vector<set<int>> vis(N+1);
    vector<int> been(N+1, 0);
    vector<int> best(N+1, -1000000000);
    priority_queue<pair<int, int>> pq;
    vis[1].insert(0);
    pq.push({0, 1});
    while (!pq.empty()) {
        int a = pq.top().second; 
        best[a] = max(best[a], pq.top().first);
        pq.pop();
        if (been[a] > 2) continue;
        while (vis[a].size() > 2) vis[a].erase(prev(vis[a].end()));
        for (int pos : vis[a]) {
            been[a]++;
            for (auto x : adj[a]) {
                if (wat[x] >= 0 && ((pos+1)%mod[wat[x]] == rem[x])) continue; 
                if (wat[a] >= 0 && wat[a] == wat[x] && (pos+1)%mod[wat[a]] == rem[a]) continue;
                vis[x].insert(pos+1);
                pq.push({-pos-1, x});
            }
            pos++;
            if (wat[a] >= 0 && pos%mod[wat[a]] == rem[a]) continue;
            for (auto x : adj[a]) {
                if (wat[x] >= 0 && ((pos+1)%mod[wat[x]] == rem[x])) continue; 
                if (wat[a] >= 0 && wat[a] == wat[x] && (pos+1)%mod[wat[a]] == rem[a]) continue;
                vis[x].insert(pos+1);
                pq.push({-pos-1, x});
            }
            pos++;
            if (wat[a] >= 0 && pos%mod[wat[a]] == rem[a]) continue;
            for (auto x : adj[a]) {
                if (wat[x] >= 0 && ((pos+1)%mod[wat[x]] == rem[x])) continue; 
                if (wat[a] >= 0 && wat[a] == wat[x] && (pos+1)%mod[wat[a]] == rem[a]) continue;
                vis[x].insert(pos+1);
                pq.push({-pos-1, x});
            }
        }
    }
    if (best[N] == -1000000000) cout << "impossible\n";
    else cout << -best[N] << "\n";
}

• Subtask 1: 0 / 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