QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#827438 | #121. Bitaro's Party | RedDiamond# | 0 | 1ms | 3824kb | C++11 | 3.0kb | 2024-12-22 23:05:20 | 2024-12-22 23:05:20 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int K = 320;
int n, m, q;
vector<vector<int>> g, gg;
vector<vector<pair<int, int>>> closest;
vector<int> vis, ord, dp;
void dfs(int u) {
vis[u] = 1;
for (auto v : g[u]) {
if (!vis[v]) {
dfs(v);
}
}
ord.push_back(u);
}
vector<bool> in;
void merge(vector<pair<int, int>> &a, vector<pair<int, int>> b) {
vector<pair<int, int>> c = a;
for (auto i : b) {
c.push_back({i.first + 1, i.second});
}
sort(rall(c));
vector<pair<int, int>> f;
for (int i = 0; i < c.size(); i += 1) {
if (in[c[i].second] == 1) {
continue;
}
f.push_back({c[i].first, c[i].second});
in[c[i].second] = 1;
if (f.size() > K) {
break;
}
}
for (auto [x, y] : f) {
in[y] = 0;
}
a = f;
}
void dfs2(int u) {
for (auto v : gg[u]) {
if (dp[u] + 1 > dp[v]) {
dp[v] = max(dp[v], dp[u] + 1);
dfs2(v);
}
}
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n >> m >> q;
g.resize(n + 1);
gg.resize(n + 1);
for (int i = 1; i <= m; i += 1) {
int e, s;
cin >> e >> s;
g[e].push_back(s);
gg[s].push_back(e);
}
vis.assign(n + 1, 0);
for (int i = 1; i <= n; i += 1) {
if (!vis[i]) {
dfs(i);
}
}
in.resize(n + 1);
reverse(all(ord));
closest.resize(n + 1);
for (auto i : ord) {
closest[i].push_back({0, i});
for (auto v : gg[i]) {
merge(closest[i], closest[v]);
}
}
dp.resize(n + 1);
vector<int> blocked(n + 1, 0);
for (int iq = 1; iq <= q; iq += 1) {
int t, y;
cin >> t >> y;
vector<int> v;
for (int j = 0; j < y; j += 1) {
int x;
cin >> x;
v.push_back(x);
blocked[x] = 1;
}
if (y > K) {
for (int i = 1; i <= n; i += 1) {
dp[i] = -1;
}
dp[t] = 0;
dfs2(t);
int ans = -1;
for (int i = 1; i <= n; i += 1) {
if (blocked[i] == 0 && i != t) {
ans = max(ans, dp[i]);
}
}
cout << ans << "\n";
} else {
int ans = -1;
for (auto i : closest[t]) {
if (!blocked[i.second] && i.second != t) {
ans = i.first;
break;
}
}
cout << ans << "\n";
}
for (auto i : v) {
blocked[i] = 0;
}
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3824kb
input:
1 0 1 1 0
output:
-1
result:
wrong answer 1st lines differ - expected: '0', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%