Submission #1214434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214434		MohamedFaresNebili	From Hacks to Snitches (BOI21_watchmen)	C++20	5 / 100	423 ms	58840 KiB

watchmen

#include <bits/stdc++.h>

        using namespace std;

        int N, M, K;
        vector<int> adj[250005];
        int DP[100005][126];
        int _L, L[155];

        int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> N >> M;
            for(int l = 1; l <= N; l++) adj[l].push_back(l);
            for(int l = 0; l < M; l++) {
                int U, V; cin >> U >> V;
                adj[U].push_back(V);
                adj[V].push_back(U);
            }

            cin >> K; cin >> _L;
            for(int l = 0; l < _L; l++) cin >> L[l];

            for(int l = 1; l <= N; l++)
                for(int i = 0; i < _L; i++)
                    DP[l][i] = 1e9 + 7;

            DP[1][0] = 0;
            queue<pair<int, int>> Q;
            Q.push({1, 0});
            while(!Q.empty()) {
                int A = Q.front().first;
                int B = Q.front().second;
                int lst = L[B];
                int cx = B;
                Q.pop();
                if(A == N) break;
                int C = DP[A][B];
                B++; B %= _L;
                int V = L[B];
                for(auto U : adj[A]) {
                    if(DP[U][B] != 1e9 + 7) continue;
                    if(U == V) continue;
                    if(U == lst && V == A) continue;
                    DP[U][B] = DP[A][cx] + 1;
                    Q.push({U, B});
                }
            }
            int res = 1e9 + 7;
            for(int l = 0; l < _L; l++)
                res = min(res, DP[N][l]);
            cout << (res == 1e9 + 7 ? -1 : res);
            return 0;
        }

• 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