| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1265245 | nguyenhuythach | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <algorithm>
#include <random>
#include <chrono>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
using namespace std;
const int nmax=1e5+69;
const int block=320;
int n,m,q;
vector<int> adj[nmax];
vector<pii> save[nmax];
int ans[nmax],vst[nmax],cnt[nmax];
vector<int> lol;
int visit[nmax];
int in_lol[nmax];
void input()
{
cin >> n >> m >> q;
FOR(i,1,m)
{
int u,v; cin >> u >> v;
adj[max(u,v)].push_back(min(u,v));
}
}
vector<pii> merge(vector<pii> &a,vector<pii> &b)
{
vector<pii> c;
int pta=0,ptb=0;
while(pta<sz(a) && ptb<sz(b))
{
if(a[pta]>b[ptb])
{
if(!cnt[a[pta].se]) c.push_back(a[pta]);
cnt[a[pta].se]++;
pta++;
}
else
{
if(!cnt[b[ptb].se]) c.push_back(b[ptb]);
cnt[b[ptb].se]++;
ptb++;
}
}
FOR(i,pta,sz(a)-1)
{
if(!cnt[a[i].se]) c.push_back(a[i]);
cnt[a[i].se]++;
}
FOR(i,ptb,sz(b)-1)
{
if(!cnt[b[i].se]) c.push_back(b[i]);
cnt[b[i].se]++;
}
FORD(i,c) cnt[i.se]=0;
while(sz(c)>block) c.pop_back();
return c;
}
void pre_dfs(int u,int v)
{
vst[u]=true;
FORD(i,adj[u])
{
if(i==v) continue;
if(!vst[i]) pre_dfs(i,u);
FOR(j,0,sz(save[i])-1) save[i][j].fi++;
save[u]=merge(save[u],save[i]);
FOR(j,0,sz(save[i])-1) save[i][j].fi--;
}
}
void build()
{
FOR(i,1,n) save[i].push_back({0,i});
REP(i,n,1) if(!vst[i]) pre_dfs(i,0);
}
void dfs(int u,int v)
{
if(visit[u]) return;
visit[u] = 1;
if(!in_lol[u]) { lol.push_back(u); in_lol[u]=1; }
FORD(i,adj[u])
{
if(i==v) continue;
dfs(i,u);
if(ans[u] != -1 && ans[i] != -1) ans[u] = max(ans[u], ans[i] + 1);
}
}
void solve()
{
build();
while(q--)
{
int t,y; cin >> t >> y;
FOR(i,1,y)
{
int x; cin >> x;
if(!in_lol[x]) { lol.push_back(x); in_lol[x]=1; }
ans[x]=-1;
}
if(y<=block)
{
bool flag=false;
FORD(i,save[t])
{
if(ans[i.se]!=-1)
{
cout << i.fi << '\n';
flag=true;
break;
}
}
if(!flag) cout << -1 << '\n';
}
else
{
dfs(t,0);
cout << ans[t] << '\n';
}
FORD(i,lol) { ans[i]=0; visit[i]=0; in_lol[i]=0; }
lol.clear();
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
solve();
return 0;
}