| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 754454 | Valters07 | 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 <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5+5;
const int B = sqrt(N)+2;
vector<int> g[N];
vector<pair<int,int> > best[N];
int dist[N];
bool dupl[N];
void merg_sort(vector<pair<int,int> > &a, vector<pair<int,int> > b)
{
for(auto &x:b)
x.fi++;
vector<pair<int,int> > nw;
int it = 0, it2 = 0;
while((it<a.size()||it2<b.size())&&nw.size()<B)
{
if(it>=a.size())
nw.pb(b[it2++]);
else if(it2>=b.size())
nw.pb(a[it++]);
else if(a[it]>b[it2])
nw.pb(a[it++]);
else
nw.pb(b[it2++]);
if(dupl[nw.back()])
nw.pop_back();
else
dupl[nw.back()]=1;
}
a.clear();
for(auto x:a)
dupl[x.se]=0;
for(auto x:b)
dupl[x.se]=0;
}
int main()
{
fio
// ifstream cin("in.in");
int n, m, q;
cin >> n >> m >> q;
while(m--)
{
int u, v;
cin >> u >> v;
g[u].pb(v);
}
for(int i = 1;i<=n;i++)
best[i].pb({0,i});
for(int i = 1;i<=n;i++)
for(auto j:g[i])
merg_sort(best[j],best[i]);
while(q--)
{
int f, y;
cin >> f >> y;
vector<int> del(y);
for(auto &x:del)
cin >> x;
if(y<B)
{
for(auto x:del)
dupl[x]=1;
int it = 0;
while(it<best[f].size()&&dupl[best[f][it].se])
it++;
if(it>=best[f].size())
cout << -1;
else
cout << best[f][it].fi;
for(auto x:del)
dupl[x]=0;
}
else
{
for(int i = 1;i<=n;i++)
dist[i]=0;
for(auto x:del)
dist[x]=-1e9;
for(int i = 1;i<=n;i++)
for(auto j:g[i])
dist[j]=max(dist[j],dist[i]+1);
if(dist[f]<0)
cout << -1;
else
cout << dist[f];
}
cout << "\n";
}
// cin.close();
return 0;
}