Submission #707466

#	Time	Username	Problem	Language	Result	Execution time	Memory
707466		EthanKim8683	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2087 ms	125028 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=100000;
const I Y=100000;
const I MAX=1e9;
const I MIN=-MAX;
vector<I>adjs[N];
vector<pair<I,I>>tops[N];
priority_queue<tuple<I,I,I,I>>ques;
I c_arr[Y];
B uses[N];
B viss[N];
B bsys[N];
I diss[N];
I tims[N];
I tim=1;
I siz;
void dfs1(I a){
  if(viss[a])return;
  viss[a]=1;
  for(auto b:adjs[a])dfs1(b);
  while(ques.size())ques.pop();
  ques.push({0,a,a,MAX});
  for(auto b:adjs[a]){
    auto[dis,x]=tops[b][0];
    ques.push({dis+1,x,b,0});
  }
  while(tops[a].size()<siz&&ques.size()){
    auto[dis1,x,b,i]=ques.top();ques.pop();
    if(!uses[x])tops[a].push_back({dis1,x}),uses[x]=1;
    if(i+1<tops[b].size()){
      auto[dis2,y]=tops[b][i+1];
      ques.push({dis2+1,y,b,i+1});
    }
  }
  for(auto[dis,x]:tops[a])uses[x]=0;
}
I dfs2(I a){
  if(tims[a]==tim)return diss[a];
  tims[a]=tim,diss[a]=bsys[a]?MIN:0;
  for(auto b:adjs[a])if(dfs2(b)!=MIN)diss[a]=max(diss[a],diss[b]+1);
  return diss[a];
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m,q;cin>>n>>m>>q;
  for(I i=0;i<m;i++){
    I s,e;cin>>s>>e,s--,e--;
    adjs[e].push_back(s);
  }
  siz=max(sqrt(n)/2.5,1.);
  for(I i=n-1;i>=0;i--)dfs1(i);
  while(q--){
    I t,y;cin>>t>>y,t--;
    for(I i=0;i<y;i++){I c;cin>>c,bsys[c_arr[i]=c-1]=1;}
    I res=MIN;
    for(auto[dis,i]:tops[t])if(!bsys[i]){res=dis;break;}
    if(res==MIN&&y>=siz)res=dfs2(t);
    printf("%i\n",dfs2(t)==MIN?-1:diss[t]),tim++;
    for(I i=0;i<y;i++)bsys[c_arr[i]]=0;
  }
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs1(I)':
bitaro.cpp:30:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'I' {aka 'int'} [-Wsign-compare]
   30 |   while(tops[a].size()<siz&&ques.size()){
      |         ~~~~~~~~~~~~~~^~~~
bitaro.cpp:33:11: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::tuple<int> >::type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if(i+1<tops[b].size()){
      |        ~~~^~~~~~~~~~~~~~~

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