Submission #703631

#TimeUsernameProblemLanguageResultExecution timeMemory
703631kinopeFrom Hacks to Snitches (BOI21_watchmen)C++14
15 / 100
6052 ms329948 KiB
#include <bits/stdc++.h> #define ff first #define ss second using namespace std; typedef pair<int, int> pii; struct info{ int x, k, mod; info(){} info(int x, int k, int mod) : x(x), k(k), mod(mod) {} }; int main(){ int n, m, a, b; scanf("%d%d", &n, &m); vector<vector<int>> g(n+1); for(int i = 0; i < m; ++i) scanf("%d%d", &a, &b), g[a].emplace_back(b), g[b].emplace_back(a); int k; scanf("%d", &k); vector<pii> ktcykl(n+1); vector<int> sz(k+1); sz[0] = 1; vector<vector<vector<int>>> dp(n+1); for(int i = 1; i <= n; ++i) dp[i].resize(k+1); for(int i = 1; i <= n; ++i) dp[i][0].emplace_back(2e09); for(int i = 1; i <= k; ++i){ scanf("%d", &b), sz[i] = b; for(int j = 1; j <= n; ++j) dp[j][i].resize(b, 2e09); for(int j = 0; j < b; ++j) scanf("%d", &a), ktcykl[a] = pii(i, j); } queue<info> q; for(int i = 0; i <= k; ++i) q.emplace(1, i, 0), dp[1][i][0] = 0; while(!q.empty()){ info x = q.front(); q.pop(); int odl = dp[x.x][x.k][x.mod]; //printf("%d %d %d: %d\n", x.x, x.k, x.mod, dp[x.x][x.k][x.mod]); if(!ktcykl[x.x].ff){ for(int u : g[x.x]){ //printf("%d %d\n", x.x, u); if(!ktcykl[u].ff) for(int i = 0; i <= k; ++i){ if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;} else if(ktcykl[u].ss != (odl+1)%sz[ktcykl[u].ff]) for(int i = 0; i <= k; ++i) if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1; } if(dp[x.x][x.k][(x.mod+1)%sz[x.k]] > odl+1) q.emplace(x.x, x.k, (x.mod+1)%sz[x.k]), dp[x.x][x.k][(x.mod+1)%sz[x.k]] = odl+1; } else{ for(int u : g[x.x]){ if(ktcykl[x.x].ff != ktcykl[u].ff){ if(!ktcykl[u].ff) for(int i = 0; i <= k; ++i){ if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1;} else if(ktcykl[u].ss != (odl+1)%sz[ktcykl[u].ff]) for(int i = 0; i <= k; ++i) if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1; } else{ if(ktcykl[u].ss == (odl+1)%sz[ktcykl[u].ff] || (ktcykl[x.x].ss == (odl+1)%sz[ktcykl[u].ff] && ktcykl[u].ss == odl%sz[ktcykl[u].ff])){/*printf("!!%d %d %d: %d %d %d\n", x.x, x.k, x.mod, u, ktcykl[x.x].ss, ktcykl[u].ss); */continue;} else for(int i = 0; i <= k; ++i) if(dp[u][i][(odl+1)%sz[i]] > odl+1) q.emplace(u, i, (odl+1)%sz[i]), dp[u][i][(odl+1)%sz[i]] = odl+1; } } if(ktcykl[x.x].ss != (odl+1)%sz[ktcykl[x.x].ff] && dp[x.x][x.k][(x.mod+1)%sz[x.k]] > odl+1) q.emplace(x.x, x.k, (x.mod+1)%sz[x.k]), dp[x.x][x.k][(x.mod+1)%sz[x.k]] = odl+1; } } int wynik = 2e09; for(int i = 0; i <= k; ++i) for(int j = 0; j < sz[i]; ++j) wynik = min(wynik, dp[n][i][j]); if(wynik == 2e09) printf("impossible\n"); else printf("%d\n", wynik); return 0; }

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   int n, m, a, b; scanf("%d%d", &n, &m);
      |                   ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:14:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   for(int i = 0; i < m; ++i) scanf("%d%d", &a, &b), g[a].emplace_back(b), g[b].emplace_back(a);
      |                              ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:15:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   int k; scanf("%d", &k);
      |          ~~~~~^~~~~~~~~~
watchmen.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d", &b), sz[i] = b;
      |     ~~~~~^~~~~~~~~~
watchmen.cpp:24:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     for(int j = 0; j < b; ++j) scanf("%d", &a), ktcykl[a] = pii(i, j);
      |                                ~~~~~^~~~~~~~~~
#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...