| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 964592 | abczz | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long
using namespace std;
vector <ll> adj[100000];
priority_queue <array<ll, 2>> pq;
queue <ll> Q;
array <ll, 2> dp[100000][330];
ll n, m, q, a, k, b, f, rt = 330, 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 >> 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});
for (int j=0; j<rt; ++j) {
dp[i][j] = {(ll)-1e18, -1};
}
for (auto u : adj[i]) {
for (int j=0; j<rt; ++j) {
if (dp[u][j][1] == -1) break;
pq.push(dp[u][j]);
}
}
for (int j=0; j<rt; ++j) {
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (ver[u] != i) {
dp[i][j] = {w+1, u};
ver[u] = 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';
}
}