| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 212535 | brcode | Bitaro’s Party (JOI18_bitaro) | C++14 | 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 <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int sqrtn = 250;
int w,e;
vector<pair<int,int>> res;
int n,m,q;
bool blocked[MAXN];
int dp[MAXN];
vector<int> v1[MAXN];
vector<int> v1rev[MAXN];
vector<pair<int,int>> temp[MAXN];
vector<int> hold;
map<int,int> m1;
void merge(vector<pair<int,int>> &a,vector<pair<int,int>> b){
for(int i=0;i<b.size();i++){
a.push_back(make_pair(b[i].first+1,b[i].second));
}
//dist,node
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
int cnt = 0;
m1.clear();
b.clear();
for(int i=0;i<a.size() && cnt<sqrtn;i++){
if(!m1[a[i].second]){
//if node not seen yet, add it to possible nodes,set it to the distance
m1[a[i].second] = a[i].first;
b.push_back(make_pair(a[i].second,0));
cnt++;
}else{
m1[a[i].second] = max(m1[a[i].second],a[i].first);
}
}
a.clear();
for(int x:b){
a.push_back(make_pair(m1[x],x);
}
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
while(a.size()>sqrtn){
a.pop_back();
}
}
int dodp(int t){
for(int i=1;i<=n;i++){
blocked[i] = false;
dp[i] = 0;
}
for(int i=0;i<hold.size();i++){
blocked[hold[i]] = true;
}
for(int i=1;i<=n;i++){
if(blocked[i]){
dp[i] = -1e9;
}else{
dp[i] = 0;
}
for(int x:v1rev[i]){
dp[i] = max(dp[i],dp[x]+1);
}
//cout<<123<<" "<<dp[i]<<endl;
}
return max(-1,dp[t]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
v1[u].push_back(v);
v1rev[v].push_back(u);
//v1rev -> backwards
}
for(int i=1;i<=n;i++){
temp[i].push_back(make_pair(0,i));
for(int x:v1rev[i]){
w=i;
e=x;
//temp[v].push_back(make_pair(1,1));
merge(temp[i],temp[x]);
//Keep merging temp[i] with nodes which connect to it to find furthest nodes
}
}
//cout<<temp[544].size()<<endl;
while(q--){
int t,c;
cin>>t>>c;
// cout<<t<<" "<<c<<endl;
hold.clear();
// set<int> s1;
for(int i=1;i<=c;i++){
int x;
cin>>x;
hold.push_back(x);
//s1.insert(x);
}
sort(hold.begin(),hold.end());
if(hold.size()>sqrtn){
cout<<dodp(t)<<"\n";
}else{
bool ok = false;
//cout<<t<<" "<<c<<endl;
if(hold.size() == 0){
if(temp[t].size()){
cout<<temp[t][0].first<<"\n";
}else{
cout<<-1<<"\n";
}
continue;
}
for(auto x:temp[t]){
// cout<<t<<" "<<c<<" "<<x.first<<" "<<x.second<<endl;
if(!binary_search(hold.begin(),hold.end(),x.second)){
cout<<x.first<<"\n";
ok = true;
break;
}
}
if(!ok){
cout<<-1<<"\n";
}
}
}
}