이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define SZ(x) ll(x.size())
const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;
const ll SQ = 100;
int n , m , q , dp2[MAXN] , mark[MAXN];
vector<int> adj[MAXN];
vector<pii> dp[MAXN];
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
for(int i = 0 ; i < m ; i++){
int v , u;
cin >> v >> u;
adj[u].push_back(v);
}
for(int i = 1 ; i <= n ; i++){
for(int j : adj[i]){
vector<pii> vec;
merge(all(dp[i]) , all(dp[j]) , back_inserter(vec) , greater<pii>());
dp[i].clear();
for(pii k : vec){
if(mark[k.Y]) continue;
dp[i].push_back(k);
mark[k.Y] = 1;
}
for(pii k : vec){
mark[k.Y] = 0;
}
if(SZ(dp[i]) > SQ){
dp[i].resize(SQ);
}
}
for(int j = 0 ; j < SZ(dp[i]) ; j++){
dp[i][j].X++;
}
if(SZ(dp[i]) < SQ){
dp[i].push_back({0 , i});
}
}
while(q--){
int v , t;
cin >> v >> t;
vector<int> vec;
for(int i = 0 ; i < t ; i++){
int x; cin >> x;
vec.push_back(x);
mark[x] = 1;
}
int ans = -1;
if(t < SQ){
for(pii i : dp[v]){
if(!mark[i.Y]){
ans = max(ans , i.X);
}
}
}
if(t >= SQ){
fill(dp2 , dp2 + MAXN , -1);
for(int i = 1 ; i <= n ; i++){
if(mark[i]) continue;
for(int j : adj[i]){
dp2[i] = max(dp2[i] , dp2[j]);
}
dp2[i]++;
}
ans = dp2[v];
}
cout << ans << endl;
for(int i : vec){
mark[i] = 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... |