이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pii;
const int maxn = 1e5 + 10;
const int sq = 110;
const int inf = 2e9;
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
vector < int > adj[maxn], radj[maxn];
vector < pii > vec[maxn];
bool nt[maxn] , c[maxn];
int n , m , q , d[maxn];
int solve(int v){
for(int i = 1 ; i < v ; i ++)
d[i] = -inf;
d[v] = 0;
for(int i = v - 1; i >= 1 ; i --)
for(auto u : adj[i])
if(u <= v)
d[i] = max(d[i] , d[u] + 1);
int ans = -1;
for(int i = 1 ; i <= v ; i ++)
if(!nt[i])
ans = max(ans , d[i]);
return(ans);
}
vector < pii > vc;
void prep(){
for(int i = 1 ; i <= n ; i ++){
vc.clear();
vc.pb({0 , i});
for(auto u : radj[i])
for(auto x : vec[u])
vc.pb({-x.first - 1 , x.second});
sort(vc.begin() , vc.end());
for(auto x : vc){
if(c[x.second])continue;
vec[i].pb({-x.first , x.second});
if(vec[i].size() == sq)break;
c[x.second] = 1;
}
for(auto x : vec[i])
c[x.second] = 0;
}
}
int32_t main(){
migmig;
cin >> n >> m >> q;
for(int i = 0 ; i < m ; i ++){
int u , v;
cin >> u >> v;
adj[u].pb(v) , radj[v].pb(u);
}
prep();
for(int i =1 ; i <= q ; i ++){
int u , v;
cin >> u >> v;
vector < int > cur;
for(int j = 0 ; j < v ; j ++){
int x;
cin >> x;
cur.pb(x);
nt[x] = 1;
}
if(v >= sq){
cout << solve(u) << endl;
for(auto x : cur)
nt[x] = 0;
continue;
}
int ans = -1;
for(auto x : vec[u]){
if(nt[x.second])continue;
ans = x.first;
break;
}
if(ans == -1){
cout << -1 << endl;
for(int x : cur)
nt[x] = 0;
continue;
}
cout << solve(u) << endl;
for(int x : cur)
nt[x] = 0;
}
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... |