| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 406531 | azberjibiou | 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>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100010;
const int mxM=320;
const int mxK=350;
const ll MOD=1000000007;
const ll INF=100000000000001;
int N, M, Q;
vector <int> v[mxN], rv[mxN];
int deg[mxN];
vector <pii> num[mxN];
vector <pii> tmpv1, tmpv2, tmpv3;
int Chk[mxN];
int idx=1;
int dp[mxN];
int main()
{
gibon
cin >> N >> M >> Q;
for(int i=1;i<=M;i++)
{
int a, b;
cin >> a >> b;
v[b].push_back(a);
}
for(int i=1;i<=N;i++)
{
if(v[i].empty()) que.push(i);
}
for(int now=1;now<=N;now++)
{
tmpv3.clear();
tmpv3.push_back({now, 0});
for(int nxt : v[now])
{
tmpv1.clear(); tmpv1.resize(tmpv3.size()); for(int i=0;i<tmpv3.size();i++) tmpv1[i]=tmpv3[i];
tmpv3.clear();
tmpv2.clear(); tmpv2.resize(num[nxt].size()); for(int i=0;i<num[nxt].size();i++) tmpv2[i]=num[nxt][i];
for(int i=0;i<tmpv2.size();i++) tmpv2[i].sec++;
int cur1=0, cur2=0;
while(cur1!=tmpv1.size() && cur2!=tmpv2.size() && tmpv3.size()<=mxK)
{
if(tmpv1[cur1].sec>tmpv2[cur2].sec)
{
if(Chk[tmpv1[cur1].fir]==idx) cur1++;
else
{
tmpv3.push_back(tmpv1[cur1]);
Chk[tmpv1[cur1++].fir]=idx;
}
}
else
{
if(Chk[tmpv2[cur2].fir]==idx) cur2++;
else
{
tmpv3.push_back(tmpv2[cur2]);
Chk[tmpv2[cur2++].fir]=idx;
}
}
}
while(tmpv3.size()<=mxK && cur1!=tmpv1.size())
{
if(Chk[tmpv1[cur1].fir]==idx) cur1++;
else tmpv3.push_back(tmpv1[cur1++]);
}
while(tmpv3.size()<=mxK && cur2!=tmpv2.size())
{
if(Chk[tmpv2[cur2].fir]==idx) cur2++;
else tmpv3.push_back(tmpv2[cur2++]);
}
idx++;
}
num[now].resize(tmpv3.size()); for(int i=0;i<tmpv3.size();i++) num[now][i]=tmpv3[i];
}
while(Q--)
{
int ans=-1;
int T, Y;
cin >> T >> Y;
for(int i=0;i<Y;i++)
{
int a; cin >> a;
Chk[a]=idx;
}
if(Y<mxK)
{
for(pii nxt : num[T]) if(Chk[nxt.fir]!=idx)
{
ans=nxt.sec;
break;
}
cout << ans << '\n';
}
else
{
for(int i=1;i<=N;i++) dp[i]=-1;
for(int now=1;now<=N;now++)
{
if(Chk[now]!=idx) dp[now]=0;
for(int nxt : v[now]) if(dp[nxt]!=-1)
{
dp[now]=max(dp[now], dp[nxt]+1);
}
}
cout << dp[T] << '\n';
}
idx++;
}
}