Submission #424884

#TimeUsernameProblemLanguageResultExecution timeMemory
424884patrikpavic2From Hacks to Snitches (BOI21_watchmen)C++17
0 / 100
112 ms42592 KiB
#include <cstdio> #include <vector> #include <cstring> #define PB push_back #define X first #define Y second using namespace std; const int N = 3e5 + 500; int rit[N], kad[N], dis[N], tko[N]; vector < int > doso[3 * N], v[N]; int n, m; bool dobar(int cv, int ds){ if(!rit[cv]) return true; return ds % rit[cv] != kad[cv]; } int main(){ memset(dis, -1, sizeof(dis)); scanf("%d%d", &n, &m); for(int i = 0;i < m;i++){ int x, y; scanf("%d%d", &x, &y); v[x].PB(y), v[y].PB(x); } int q; scanf("%d", &q); for(;q--;){ int ln; scanf("%d", &ln); for(int i = 0;i < ln;i++){ int x; scanf("%d", &x); rit[x] = ln, kad[x] = i; tko[x] = q + 1; } } doso[0].PB(1); for(int i = 0;i < 3 * N;i++){ for(int x : doso[i]){ if(dis[x] != -1) continue; dis[x] = i; for(int k = 0;k < 3;k++){ if(!dobar(x, dis[x] + k)) break; for(int y : v[x]){ if((tko[x] != tko[y] || !tko[x]) && dobar(y, dis[x] + k + 1)) doso[dis[x] + k + 1].PB(y); if(tko[x] == tko[y] && dobar(y, dis[x] + k + 1) && !(kad[x] == (kad[y] + 1) % rit[x] && !dobar(y, dis[x] + k))) doso[dis[x] + k + 1].PB(y); } } } } if(dis[n] == -1) printf("impossible\n"); else printf("%d\n", dis[n]); return 0; }

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:31:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   int ln; scanf("%d", &ln);
      |           ~~~~~^~~~~~~~~~~
watchmen.cpp:33:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...