Submission #528060

#	Time	Username	Problem	Language	Result	Execution time	Memory
528060		qwerasdfzxcl	From Hacks to Snitches (BOI21_watchmen)	C++14	5 / 100	1039 ms	55932 KiB

watchmen

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int INF = 1e9;
int dist[100100][125], a[125];
vector<int> adj[100100];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++) adj[i].push_back(i);
    for (int i=0;i<m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int k, x;
    scanf("%d", &k);
    for (int i=0;i<k;i++){
        scanf("%d", &x);
        for (int j=0;j<x;j++) scanf("%d", a+j);
    }

    for (int i=1;i<=n;i++) fill(dist[i], dist[i]+125, INF);
    dist[1][0] = 0;
    queue<pair<int, int>> q;
    q.emplace(1, 0);
    while(!q.empty()){
        auto p = q.front(); q.pop();
        //printf("%d %d: %d\n", p.first, p.second, dist[p.first][p.second]);
        int ct = p.second, nt = p.second + 1;
        if (nt>=x) nt = 0;
        for (auto &v:adj[p.first]){
            if (a[nt]==v) continue;
            if (a[ct]==v && a[nt]==p.first) continue;
            if (dist[v][nt] <= dist[p.first][p.second] + 1) continue;

            dist[v][nt] = dist[p.first][p.second] + 1;
            q.emplace(v, nt);
        }
    }

    int ans = *min_element(dist[n], dist[n]+125);
    if (ans==INF) printf("impossible\n");
    else printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
watchmen.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:23:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         for (int j=0;j<x;j++) scanf("%d", a+j);
      |                               ~~~~~^~~~~~~~~~~

• 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