이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |