| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1084805 | DucNguyen2007 | 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>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
vector<int> adj[maxN+1],topo;
vector<pii> vec[maxN+1];
bool vis[maxN+1];
void dfs(int u)
{
vis[u]=true;
for(auto v:adj[u])
{
if(!vis[v])
{
dfs(v);
}
}
topo.push_back(u);
}
void meg(int u,int v)
{
vector<pii> vt;
int i=0,j=0;
for(auto i:vec[u])
{
vis[i.fi]=false;
}
for(auto i:vec[v])
{
vis[i.fi]=false;
}
while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
{
while(i<vec[u].size()&&vis[vec[u][i].fi])
{
i++;
}
while(j<vec[v].size()&&vis[vec[v][j].fi])
{
j++;
}
if(i>=vec[u].size()||j>=vec[v].size())
{
break;
}
int p1=vec[u][i].se,p2=vec[v][j].se;
if(p1+1>p2)
{
vt.push_back({vec[u][i].fi,p1+1});
vis[vec[u][i].fi]=true;
i++;
}
else
{
vt.push_back({vec[v][j].fi,p2});
vis[vec[v][j].fi]=true;
j++;
}
}
while(i<vec[u].size()&&vt.size()<block)
{
while(i<vec[u].size()&&vis[vec[u][i].fi])
{
i++;
}
if(i>=vec[u].size())
{
break;
}
vt.push_back({vec[u][i].fi,vec[u][i].se+1});
i++;
}
while(j<vec[v].size()&&vt.size()<block)
{
while(j<vec[v].size()&&vis[vec[v][j].fi])
{
j++;
}
if(j>=vec[v].size())
{
break;
}
vt.push_back({vec[v][j].fi,vec[v][j].se});
j++;
}
vec[v]=vt;
}
void make()
{
for(auto u:topo)
{
vec[u].push_back({u,0});
for(auto v:adj[u])
{
//cout<<u<<" "<<v<<'\n';
meg(u,v);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
}
block=sqrt(n);
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs(i);
}
}
memset(dp,0,sizeof(dp));
reverse(topo.begin(),topo.end());
make();
while(q--)
{
int t,y;
cin>>t>>y;
if(y>=block)
{
for(int i=1;i<=n;i++)
{
dp[i]=0;
}
}
for(int i=1;i<=y;i++)
{
int u;
cin>>u;
a[i]=u;
dp[u]=INT_MIN;
if(y<block)
{
cnt[u]++;
}
}
if(y>=block)
{
for(auto u:topo)
{
for(auto v:adj[u])
{
dp[v]=max(dp[v],dp[u]+1);
}
}
if(dp[t]<0)
{
cout<<-1;
}
else cout<<dp[t];
}
else
{
int ans=-1;
for(auto u:vec[t])
{
if(!cnt[u.fi])
{
ans=u.se;
break;
}
}
cout<<ans;
}
cout<<'\n';
for(int i=1;i<=y;i++)
{
cnt[a[i]]=0;
}
}
}
/*4 8 5
2 3
2 3
1 3
1 3
3 4
1 2
1 2
1 2
2 1 4
1 3 4 2 2
3 4 1 1 4 2
4 2 1 3
3 1 4*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
int n,m,q,dp[maxN+1],block,a[maxN+1],cnt[maxN+1];
vector<int> adj[maxN+1],topo;
vector<pii> vec[maxN+1];
bool vis[maxN+1];
void dfs(int u)
{
vis[u]=true;
for(auto v:adj[u])
{
if(!vis[v])
{
dfs(v);
}
}
topo.push_back(u);
}
void meg(int u,int v)
{
vector<pii> vt;
int i=0,j=0;
for(auto i:vec[u])
{
vis[i.fi]=false;
}
for(auto i:vec[v])
{
vis[i.fi]=false;
}
while(i<vec[u].size()&&j<vec[v].size()&&vt.size()<block)
{
while(i<vec[u].size()&&vis[vec[u][i].fi])
{
i++;
}
while(j<vec[v].size()&&vis[vec[v][j].fi])
{
j++;
}
if(i>=vec[u].size()||j>=vec[v].size())
{
break;
}
int p1=vec[u][i].se,p2=vec[v][j].se;
if(p1+1>p2)
{
vt.push_back({vec[u][i].fi,p1+1});
vis[vec[u][i].fi]=true;
i++;
}
else
{
vt.push_back({vec[v][j].fi,p2});
vis[vec[v][j].fi]=true;
j++;
}
}
while(i<vec[u].size()&&vt.size()<block)
{
while(i<vec[u].size()&&vis[vec[u][i].fi])
{
i++;
}
if(i>=vec[u].size())
{
break;
}
vt.push_back({vec[u][i].fi,vec[u][i].se+1});
i++;
}
while(j<vec[v].size()&&vt.size()<block)
{
while(j<vec[v].size()&&vis[vec[v][j].fi])
{
j++;
}
if(j>=vec[v].size())
{
break;
}
vt.push_back({vec[v][j].fi,vec[v][j].se});
j++;
}
vec[v]=vt;
}
void make()
{
for(auto u:topo)
{
vec[u].push_back({u,0});
for(auto v:adj[u])
{
//cout<<u<<" "<<v<<'\n';
meg(u,v);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
}
block=sqrt(n);
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs(i);
}
}
memset(dp,0,sizeof(dp));
reverse(topo.begin(),topo.end());
make();
while(q--)
{
int t,y;
cin>>t>>y;
if(y>=block)
{
for(int i=1;i<=n;i++)
{
dp[i]=0;
}
}
for(int i=1;i<=y;i++)
{
int u;
cin>>u;
a[i]=u;
dp[u]=INT_MIN;
if(y<block)
{
cnt[u]++;
}
}
if(y>=block)
{
for(auto u:topo)
{
for(auto v:adj[u])
{
dp[v]=max(dp[v],dp[u]+1);
}
}
if(dp[t]<0)
{
cout<<-1;
}
else cout<<dp[t];
}
else
{
int ans=-1;
for(auto u:vec[t])
{
if(!cnt[u.fi])
{
ans=u.se;
break;
}
}
cout<<ans;
}
cout<<'\n';
for(int i=1;i<=y;i++)
{
cnt[a[i]]=0;
}
}
}