이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
int block = 316;
#define pii pair<int, int>
#define fr first
#define se second
vector<vector<pii>> far;
vector<bool> freq;
pii aux[500];
void merge(int from, int to) {
vector<pii> leaving;
for (auto u : far[from]) {
leaving.push_back({u.fr + 1, u.se});
}
for (auto u : leaving) {
freq[u.se] = 0;
}
for (auto u : far[to]) {
freq[u.se] = 0;
}
int p1 = 0, p2 = 0;
int n = leaving.size();
int m = far[to].size();
int s = 0;
while ((s < 316) && ((p1 < n) || (p2 < m))) {
if (p1 == n) {
// check p2
if (freq[far[to][p2].se]) {
p2++;
continue;
}
aux[s] = far[to][p2];
freq[far[to][p2].se] = 1;
p2++;
} else if (p2 == m) {
// check p1
if (freq[leaving[p1].se]) {
p1++;
continue;
}
aux[s] = leaving[p1];
freq[leaving[p1].se] = 1;
p1++;
} else {
if (freq[leaving[p1].se]) {
p1++;
continue;
}
if (freq[far[to][p2].se]) {
p2++;
continue;
}
if (leaving[p1] > far[to][p2]) {
aux[s] = leaving[p1];
freq[leaving[p1].se] = 1;
p1++;
} else {
aux[s] = far[to][p2];
freq[far[to][p2].se] = 1;
p2++;
}
}
s++;
}
for (int i = 0; i < s; i++) {
if (i < m) {
far[to][i] = aux[i];
} else {
far[to].push_back(aux[i]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> adj(n + 1);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
far.resize(n + 1);
freq.resize(n + 1);
for (int i = 1; i <= n; i++) {
far[i].push_back({0, i});
}
for (int i = 1; i <= n; i++) {
for (auto u : adj[i]) {
merge(i, u);
}
}
// process all 316 farthest nodes
while (q--) {
int t, y;
cin >> t >> y;
if (y >= block) {
// At most MsqrtN
vector<int> mx(t + 1);
while (y--) {
int a;
cin >> a;
mx[a] = -1;
}
for (int i = 1; i <= t; i++) {
if (mx[i] == -1) continue;
for (auto u : adj[i]) {
mx[u] = max(mx[u], mx[i] + 1);
}
}
cout << mx[t] << "\n";
} else {
// at most sqrtN
map<int, bool> map;
while (y--) {
int a;
cin >> a;
map[a] = 1;
}
bool good = 0;
for (auto u : far[t]) {
if (!map[u.se]) {
cout << u.fr << "\n";
good = 1;
break;
}
}
if (!good) {
cout << "-1\n";
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |