| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314038 | m.h.n | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e5 + 100;
int k;
vector <int> add[maxn];
vector <int> rem[maxn];
set <pii> st[maxn];
set <pii> stt[maxn];
int dp[maxn];
void dfs( int x ){
for( auto u : rem[x] ){
for( auto p : st[u] ){
pii tmp = p;
auto ss = stt[x].lower_bound({tmp.second,-1});
if(ss != stt[x].end() && ss->first == tmp.second){
pii dd = *ss;
if(dd.second < tmp.first+1){
auto it = st[x].find({dd.second,dd.first});
if(it != st[x].end()) st[x].erase(it);
stt[x].erase(ss);
st[x].insert({tmp.first+1,tmp.second});
stt[x].insert({tmp.second,tmp.first+1});
}
}
else{
st[x].insert({tmp.first+1,tmp.second});
stt[x].insert({tmp.second,tmp.first+1});
}
}
st[x].insert({1,u});
stt[x].insert({u,1});
}
st[x].insert({0,x});
stt[x].insert({x,0});
while(st[x].size()>k){
pii ss = *st[x].begin();
st[x].erase(ss);
stt[x].erase({ss.second,ss.first});
}
return;
}
void ddfs( int x ){
for( auto u : add[x] ){
if(dp[u]==-1e9)
continue;
if(dp[x]<dp[u]+1){
dp[x] = dp[u] + 1;
}
}
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m,q;
cin >> n >> m >> q;
k = sqrt(n)+1;
for( int i = 1; i <= m; i++ ){
int u,v;
cin >> u >> v;
add[u].push_back(v);
rem[v].push_back(u);
}
for( int i = 1; i <= n; i++ )
dfs(i);
while(q--){
int u;
cin >> u;
set <int> no;
int tt;
cin >> tt;
for( int i = 1; i <= tt; i++ ){
int v;
cin >> v;
no.insert(v);
}
if(no.size()<k){
int ans = 0;
for( auto p : st[u] ){
if( no.find(p.second) == no.end() ){
ans = max(ans,p.first);
}
}
cout << ans << '\n';
}
else{
for( int i = 1; i <= n; i++ )
dp[i] = -1e9;
dp[u] = 0;
for( int i = u; i > 0; i-- )
ddfs(i);
int ans = -1e9;
for( int i = 1; i <= u; i++ ){
if(!no.count(i)){
ans = max(ans,dp[i]);
}
}
cout << ans << '\n';
}
}
}