제출 #95086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95086		Mahdi_Jfri	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1175 ms	127924 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

typedef int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;

#define RETD(x) cout << fixed << setprecision(15) << x;
#define X first
#define Y second
#define PB push_back
#define For(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) ((ll)(x.size()))
#define smax(a,b) a=max(a,b)
#define ER(x) cout << #x << ' ' << x << '\n'
#define MKP make_pair
#define smin(a,b) a=min(a,b);

const ll M=1e5+5,inf=1e9,SM=100;

typedef complex<ld> point;

pair<ld,point> p[M];

ll n,m,q;
vector<pll> dp[M];
ll res[M];
vector<ll> g[M];

void merg(ll x,ll y){
  for(pll f:dp[x]){
    res[f.Y]=f.X;
  }
  for(pll f:dp[y]){
    smin(res[f.Y],f.X-1);
  }
  For(i,0,SZ(dp[x])){
    dp[x][i].X=res[dp[x][i].Y];
    res[dp[x][i].Y]=0;
  }
  For(i,0,SZ(dp[y])){
    if (res[dp[y][i].Y]){
      dp[x].PB({dp[y][i].X-1,dp[y][i].Y});
      res[dp[y][i].Y]=0;
    }
  }
  sort(dp[x].begin(),dp[x].end());
  while (SZ(dp[x])>SM) dp[x].pop_back();
}

vll qud;
ll mark[M];
ll tmp[M];

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m >> q;
  For(i,0,m){
    ll u,v;
    cin >> u >> v;
    u--;v--;
    g[v].PB(u);
  }
  For(x,0,n){
    //ER(x);
    for (ll y:g[x]){
      //ER(y);
      merg(x,y);
    }
    if (SZ(dp[x])<SM){
      dp[x].PB({0,x});
    }
  }
  while (q--){
    //ER(q);
    ll v,c;
    cin >> v >> c;
    v--;
    For(i,0,c){
      ll x;
      cin >> x;
      x--;
      qud.PB(x);
      mark[x]=1;
    }
    if (c<SM){
      bool ah=0;
      for (pll x:dp[v]){
	//ER(x.Y << ' ' << mark[x.Y]);
	if (!mark[x.Y]){
	  cout << -x.X << '\n';
	  ah=1;
	  break;
	}
      }
      if (!ah) cout << "-1\n";
    }else{
      For(i,0,v+1){
	tmp[i]=0;
	if (mark[i]){
	  tmp[i]=-1;
	}
	for (ll y:g[i]){
	  if (tmp[y]==-1) continue;
	  smax(tmp[i],tmp[y]+1);
	}
      }
      cout << tmp[v] << '\n';
    }
    for (ll f:qud){
      mark[f]=0;
    }
    qud.clear();
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86