| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 854943 | parlimoos | Bitaro’s Party (JOI18_bitaro) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int root = 320;
int n , m , q , r;
vector<int> g[100000];
vector<pair<int , int>> lps[100000];
int dels[100000];
int dis[100000];
int ddd[100000][2];
void init(){
for(int i = 0 ; i < n ; i++){
vector<int> exs;
lps[i].push_back({0 , i});
exs.push_back(i);
ddd[i][0] = 0;
ddd[i][1] = i + 1;
for(int v : g[i]){
for(pair<int , int> el : lps[v]){
if(ddd[el.second][1] != i + 1){
exs.push_back(el.second);
ddd[el.second][1] = i + 1;
ddd[el.second][0] = el.first + 1;
}else ddd[el.second][0] = max(ddd[el.second] , el.first + 1);
}
}
for(int v : g[i]){
for(int el : exs){
lps[i].push_back({ddd[el][0] , el});
}
sort(lps[i].begin() , lps[i].end() , [](pair<int , int> a , pair<int , int>b){
return (a.first > b.first);
});
int len = (int)lps[i].size();
while(len > root){
lps[i].pop_back();
len--;
}
}
}
}
void bfs(int op){
fill(&dis[0] , &dis[100000] , 0);
for(int i = 0 ; i <= r ; i++){
for(int u : g[i]){
dis[i] = max(dis[u] + 1 , dis[i]);
}
if(dis[i] == 0 and dels[i] == op){
dis[i] = -1;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for(int i = 0 ; i < m ; i++){
int v , u;
cin >> v >> u;
v-- , u--;
g[u].push_back(v);
}
if(q > 1) init();
for(int i = 0 ; i < q ; i++){
int y;
cin >> r >> y;
r--;
for(int j = 0 ; j < y ; j++){
int d;
cin >> d;
d--;
dels[d] = i + 1;
}
if(y >= root or q == 1){
bfs(i + 1);
cout << dis[r] << "\n";
}else{
int res = -1;
for(int j = 0 ; j < (int)lps[r].size() ; j++){
if(dels[lps[r][j].second] != i + 1){
res = lps[r][j].first;
break;
}
}
cout << res << "\n";
}
}
}