제출 #964604

#제출 시각아이디문제언어결과실행 시간메모리
964604abczzBitaro’s Party (JOI18_bitaro)C++14
14 / 100
989 ms272544 KiB
#include <iostream> #include <vector> #include <array> #include <queue> #define ll int using namespace std; vector <ll> adj[100000]; priority_queue <array<ll, 3>> pq; queue <ll> Q; array <ll, 2> dp[100000][330]; ll n, m, q, a, k, b, f, rt = 200, dist[100000], B[100000], in[100000], visited[100000], ver[100000]; void dfs(ll u) { visited[u] = q; in[u] = 0; for (auto v : adj[u]) { if (visited[v] != q) dfs(v); ++in[v]; } } int main() { cin.tie(0); ios::sync_with_stdio(0); cin >> n >> m >> q; for (int i=0; i<m; ++i) { cin >> a >> b; --a, --b; adj[b].push_back(a); } for (int i=0; i<n; ++i) { B[i] = visited[i] = ver[i] = -1; while (!pq.empty()) pq.pop(); pq.push({-1, i, -1}); for (int j=0; j<rt; ++j) { dp[i][j] = {(ll)-1e9, -1}; } for (auto u : adj[i]) { pq.push({dp[u][0][0], u, 0}); } for (int j=0; j<rt; ++j) { while (!pq.empty()) { auto [w, u, x] = pq.top(); pq.pop(); if (x != -1 && x != rt-1 && dp[u][x+1][1] != -1) { pq.push({dp[u][x+1][0], u, x+1}); } if (x == -1) { dp[i][j] = {w+1, u}; break; } else if (ver[dp[u][x][1]] != i) { dp[i][j] = {w+1, dp[u][x][1]}; ver[dp[u][x][1]] = i; break; } } } } while (q--) { cin >> a >> k; --a; for (int i=0; i<k; ++i) { cin >> b; --b; B[b] = q; } if (k < rt) { for (int i=0; i<rt; ++i) { if (dp[a][i][1] == -1) { cout << "-1\n"; break; } if (B[dp[a][i][1]] != q) { cout << dp[a][i][0] << '\n'; break; } } } else { dfs(a); Q.push(a); dist[a] = 0; f = -1; while (!Q.empty()) { auto u = Q.front(); Q.pop(); if (B[u] != q) f = max(f, dist[u]); for (auto v : adj[u]) { --in[v]; dist[v] = max(dist[v], dist[u]+1); if (!in[v]) Q.push(v); } } cout << f << '\n'; } } }

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [w, u, x] = pq.top();
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...