이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define int long long
#define ll long long
#define pii pair<int,int>
#define ar array
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
template<class T> using st = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;
int binpow(int a, int b){
if(b == 0)return 1;
if(b % 2 == 0){
int c = binpow(a,b/2);
return (c*c)%mod;
}
return (binpow(a,b-1)*a)%mod;
}
int divi(int a, int b){
return (a*(binpow(b,mod-2)))%mod;
}
int n,m,k;
int sz = 400;
vector<int>g[N];
vector<ar<int,2>>calc[N];
void solve(){
cin >> n >> m >> k;
while(m--){
int a,b;
cin >> a >> b;
//~ g[a].pb(b);
g[b].pb(a);
}
vector<int>reach, dist(n+1), last(n+1);
for(int i = 1;i<=n;i++){
reach.pb(i);
for(auto x:g[i]){
for(auto [cost, to] : calc[x]){
if(last[to] == i){
umax(dist[to], cost + 1);
} else {
dist[to] = cost + 1;
last[to] = i;
reach.pb(to);
}
}
}
sort(all(reach),[&](int a, int b){
return dist[a] > dist[b];
});
for(int j = 0;j<min(sz, (int)reach.size());j++){
calc[i].pb({dist[reach[j]],reach[j]});
}
reach.clear();
}
vector<int>vis(n+1);
while(k--){
int a,b,c;
cin >> a >> b;
vector<int>vs;
for(int i = 1;i<=b;i++){
cin >> c;
vis[c] = 1;
vs.pb(c);
}
if(b > sz){
vector<int>dist(n+1);
queue<int>q;
q.push(a);
while(!q.empty()){
auto x = q.front();
q.pop();
for(auto to:g[x]){
if(umax(dist[to], dist[x] + 1)){
q.push(to);
}
}
}
int mx = -1;
for(int i = 1;i<=n;i++){
if(vis[i] || dist[i] == 0 && i != a)continue;
umax(mx, dist[i]);
}
cout << mx << "\n";
}
else{
for(auto [cost, to] : calc[a]){
if(vis[to])continue;
cout << cost << "\n";
break;
}
}
for(auto to:vs)vis[to] = 0;
}
}
/*
5 6 1
5 3
5 4
3 1
3 2
4 2
2 1
2 1 5
1 2 3 4
4 3 1 2 5
*/
signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt=1;//cin>>tt;
while(tt--)solve();
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'void solve()':
bitaro.cpp:112:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
112 | if(vis[i] || dist[i] == 0 && i != a)continue;
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |