이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5;
int n, m, q;
vector<int> adj[N];
vector<pair<int, int>> far[N];
void pre() {
for (int i = 0; i < n; i++) {
priority_queue<pair<int, int>> pq;
for (int j : adj[i]) {
for (auto k : far[j])
pq.push(k);
}
unordered_set<int> s;
for (int j = 0; j <= ceil(sqrt(n)) && !pq.empty();) {
auto temp = pq.top();
pq.pop();
if (!s.count(temp.second)) {
far[i].emplace_back(temp.first + 1, temp.second);
s.insert(temp.second);
j++;
}
}
if (far[i].size() <= ceil(sqrt(n)))
far[i].emplace_back(0, i);
}
}
int calc(int t, const set<int>& c) {
int dp[n] = {};
fill(dp, dp + n, -1);
dp[t] = 0;
for (int i = t; i >= 0; i--) {
for (int j : adj[i])
dp[j] = max(dp[j], dp[i] + 1);
}
int ans = -1;
for (int i = t; i >= 0; i--) {
if (!c.count(i))
ans = max(ans, dp[i]);
}
return ans;
}
int find(int t, const set<int>& c) {
for (auto i : far[t]) {
if (!c.count(i.second))
return i.first;
}
return -1;
}
int solveTestCase(int test) {
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int s = 0, e = 0;
cin >> s >> e;
s--, e--;
adj[e].push_back(s);
}
pre();
for (int i = 0; i < q; i++) {
int t = 0, y = 0;
cin >> t >> y;
set<int> c;
for (int j = 0; j < y; j++) {
int temp = 0;
cin >> temp;
c.insert(temp - 1);
}
if (y >= ceil(sqrt(n)))
cout << calc(t - 1, c) << "\n";
else
cout << find(t - 1, c) << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
//cin >> test;
for (int i = 1; i <= test; i++)
solveTestCase(i);
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'long long int solveTestCase(long long int)':
bitaro.cpp:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |