이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int BLOCK_SZ = 400;
int n,m,q;
vector<int> adj[MAXN+1]; // rev_adj
vector<pair<int,int>> mx_dis[MAXN+1];
void precomp() {
for (int u=1;u<=n;u++) {
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push(make_pair(0,u));
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i];
vector<pair<int,int>> &vec = mx_dis[v];
for (int j=vec.size();j>=0;j--) {
pair<int,int> cur = vec[j];
cur.first++;
if (pq.size() < BLOCK_SZ || cur.first > pq.top().first) {
if (pq.size() == BLOCK_SZ) pq.pop();
pq.push(cur);
}
else if (cur.first <= pq.top().first) break;
}
}
while (pq.size()) {
// cerr << u << ' ' << pq.top().first << ' ' << pq.top().second << '\n';
mx_dis[u].push_back(pq.top());
pq.pop();
}
}
}
int dp[MAXN+1];
bool no_no[MAXN+1];
int query_big(int id) {
memset(dp,-1,sizeof(dp));
for (int i=1;i<=id;i++) {
if (!no_no[i]) dp[i] = 0;
for (int j=0;j<adj[i].size();j++) {
int v = adj[i][j];
if (dp[v] == -1) continue;
dp[i] = max(dp[i],dp[v] + 1);
}
}
return dp[id];
}
int query(int id) {
for (int i=mx_dis[id].size()-1;i>=0;i--) {
if (!no_no[mx_dis[id][i].second]) return mx_dis[id][i].first;
}
if (mx_dis[id].size() < BLOCK_SZ) return -1;
return query_big(id);
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m >> q;
for (int i=1;i<=m;i++) {
int x,y; cin >> x >> y;
adj[y].push_back(x);
}
precomp();
while (q--) {
int t,y;
vector<int> c;
cin >> t >> y;
for (int i=0;i<y;i++) {
int x; cin >> x;
c.push_back(x);
no_no[x] = 1;
}
cout << query(t) << '\n';
for (int i=0;i<y;i++) no_no[c[i]] = 0;
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'void precomp()':
bitaro.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int query_big(int)':
bitaro.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int j=0;j<adj[i].size();j++) {
| ~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |