이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
const int SZ = 100;
int n, m, q, a, b;
cin >> n >> m >> q;
vvi adj(n), radj(n);
for(int i = 0; i < m; i++){
cin >> a >> b;
adj[--a].emplace_back(--b);
radj[b].emplace_back(a);
}
vector<vector<pii>> bestSZ(n);
vi starting(n, -1);
for(int v = 0; v < n; v++){ // Duplicates are the issue
vi from;
bestSZ[v].emplace_back(0, v);
for(int &u : radj[v]){
for(pii &d : bestSZ[u]){
if(starting[d.se] == -1){
from.emplace_back(d.se);
starting[d.se] = d.fi + 1;
}
else{
starting[d.se] = max(starting[d.se], d.fi + 1);
}
}
}
for(int &u : from){
bestSZ[v].emplace_back(starting[u], u);
}
sort(bestSZ[v].begin(), bestSZ[v].end(), greater<pii>());
while(sz(bestSZ[v]) > SZ){
bestSZ[v].pop_back();
}
for(int &u : from){
starting[u] = -1;
}
}
vb can(n, true);
while(q--){
int t, y, ans = -1;
cin >> t >> y;
t--;
vi yi(y);
for(int i = 0; i < y; i++){
cin >> yi[i];
can[--yi[i]] = false;
}
if(y >= SZ){
vi dp(t + 1, -1);
dp[t] = 0;
for(int v = t; v >= 0; v--){
if(dp[v] == -1) continue;
if(can[v]) ans = max(ans, dp[v]);
for(int &u : radj[v]){
dp[u] = max(dp[u], dp[v] + 1);
}
}
}
else{
for(pii &p : bestSZ[t]){
if(can[p.se]){
ans = p.fi;
break;
}
}
}
for(int i = 0; i < y; i++){
can[yi[i]] = true;
}
cout << ans << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |