제출 #409050

#제출 시각아이디문제언어결과실행 시간메모리
409050Kevin_Zhang_TWFrom Hacks to Snitches (BOI21_watchmen)C++17
35 / 100
1880 ms98924 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif using t3 = pair<ll,int>; const int MAX_N = 300010, MAX_K = 2800, hol = 100; const ll inf = 1ll << 55; int n, m; vector<int> edge[MAX_N], cyc[MAX_N]; ll dp[MAX_N][2]; int cid[MAX_N], csz[MAX_N], cpos[MAX_N]; int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); // init everything cin >> n >> m; for (int a, b, i = 0;i < m;++i) { cin >> a >> b; edge[a].pb(b); edge[b].pb(a); } for (int i = 1;i <= n;++i) { dp[i][0] = dp[i][1] = inf; csz[i] = 1; } int K; cin >> K; for (int i = 1;i <= K;++i) { int len; cin >> len; cyc[i].resize(len); int c = 0; for (int &u : cyc[i]) { cin >> u; cid[u] = i; csz[u] = len; cpos[u] = c++; } } //priority_queue<t3, vector<t3>, greater<t3>> q; //queue<pair<ll,int>> q; vector<vector<int>> q; auto putin = [&](int d, int x) { if (q.size() < d + 1) q.resize(d + 1); q[d].pb(x); }; // > d, when will x be hit auto behit = [&](int x, ll d) { if (cid[x] == 0) return inf; ll a = d % csz[x], b = cpos[x]; if (a <= b) return d + b - a; return d + csz[x] - a + b; }; auto upd = [&](int x, ll d) { auto &A = dp[x][0], &B = dp[x][1]; bool ch = false; if (d < A) { putin(d, x); swap(d, A); ch = true; } if (cid[x] == 0) return; if (d > behit(x, A) && d < B) { if (!ch) putin(d, x); swap(B, d); } }; upd(1, 0); // when x's shortest path is d, I want to relax u auto valid = [&](int x, ll d, int u) { if (cid[u] == 0) return true; if (d % csz[u] == cpos[u]) return false; if (cid[x] == cid[u] && cpos[u] == (cpos[x] - 1 + csz[x]) % csz[u]) { if (d % csz[u] == cpos[x]) return false; } return true; }; auto relax = [&](int x, int u, ll d) { if (cid[u] == 0) { upd(u, d+1); return; }; DE(x, u, d); if (valid(x, d+1, u)) upd(u, d+1); else if (valid(x, d+1, x) && valid(x, d+2, u)) upd(u, d+2); ll xh = behit(x, d), uh = behit(u, d); if (xh <= uh + 1) return; DE(xh, uh, x, u, d); upd(u, uh + 1); }; // shortest path for (int d = 0;d < q.size();++d) { for (int i = 0;i < q[d].size();++i) { int x = q[d][i]; if (d != dp[x][0] && d != dp[x][1]) continue; if (cid[x]) assert(d % csz[x] != cpos[x]); DE(d, x); for (int u : edge[x]) relax(x, u, d); } } ll res = inf; for (auto v : dp[n]) chmin(res, v); if (res == inf) cout << "impossible\n"; else cout << res << '\n'; }

컴파일 시 표준 에러 (stderr) 메시지

watchmen.cpp: In lambda function:
watchmen.cpp:62:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   if (q.size() < d + 1) q.resize(d + 1);
      |       ~~~~~~~~~^~~~~~~
watchmen.cpp: In lambda function:
watchmen.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
watchmen.cpp:106:3: note: in expansion of macro 'DE'
  106 |   DE(x, u, d);
      |   ^~
watchmen.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
watchmen.cpp:114:3: note: in expansion of macro 'DE'
  114 |   DE(xh, uh, x, u, d);
      |   ^~
watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for (int d = 0;d < q.size();++d) {
      |                 ~~^~~~~~~~~~
watchmen.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for (int i = 0;i < q[d].size();++i) {
      |                  ~~^~~~~~~~~~~~~
watchmen.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
watchmen.cpp:126:4: note: in expansion of macro 'DE'
  126 |    DE(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...