| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 212849 | 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int MAXN = 2e5+5;
const int sqrtn = 110;
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;
int m1[MAXN];vector<pair<int,int>> c;
void merge(vector<pair<int,int>> &a,vector<pair<int,int>> b){
c.clear();
int ind = 0;
for(int i=0;i<b.size();i++){
while(ind<a.size() && a[ind].first>=b[i].first+1){
c.push_back(make_pair(a[ind].first,a[ind].second));
ind++;
}
c.push_back(make_pair(b[i].first+1,b[i].second));
}
while(ind<a.size()){
c.push_back(make_pair(a[ind].first,a[ind].second));
ind++;
}
int cnt = 0;
for(int i=0;i<c.size();i++){
//cout<<e<<" "<<w<<" "<<c[i].first<<" "<<c[i].second<<endl;
if(m1[c[i].second]){
m1[c[i].second] = 0;
}
}
b.clear();
for(int i=0;i<c.size() && cnt<sqrtn;i++){
if(!m1[c[i].second]){
//if node not seen yet, add it to possible nodes,set it to the distance
m1[c[i].second] = c[i].first;
b.push_back(make_pair(c[i].second,0));
cnt++;
}else{
m1[c[i].second] = max(m1[c[i].second],c[i].first);
}
}
a.clear();
for(auto x:b){
a.push_back(make_pair(m1[x.first],x.first));
}
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]){
//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[i][0].first<<endl;
}
// cout<<123<<endl;
for(int i=1;i<=n;i++){
m1[i] = -1;
}
//cout<<cnt3<<endl;
//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);
m1[x] = q;
//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;
}
// sort(hold.begin(),hold.end());
for(auto x:temp[t]){
// cout<<t<<" "<<c<<" "<<x.first<<" "<<x.second<<endl;
if(m1[x.second]!=q){
cout<<x.first<<"\n";
ok = true;
break;
}
}
if(!ok){
cout<<-1<<"\n";
}
}
}
}