Submission #707449

#	Time	Username	Problem	Language	Result	Execution time	Memory
707449		EthanKim8683	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2069 ms	4948 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=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;
set<I>curs;
B viss[N];
set<I>uses;
I diss[N];
I tims[N];
I tim=1;
I siz;
void dfs1(I a){
  if(viss[a])return;
  viss[a]=1;
  while(ques.size())ques.pop();
  ques.push({0,a,a,MAX});
  for(auto b:adjs[a]){
    dfs1(b);
    auto[dis,y]=tops[b][0];
    ques.push({dis+1,y,b,0});
  }
  uses.clear();
  while(tops[a].size()<siz){
    auto[dis,y,x,i]=ques.top();ques.pop();
    if(uses.count(y))continue;
    uses.insert(y);
    tops[a].push_back({dis,y});
    if(i+1<tops[x].size()){
      auto[dis,z]=tops[x][i+1];
      ques.push({dis+1,z,x,i+1});
    }
  }
}
I dfs2(I a){
  if(tims[a]==tim)return diss[a];
  tims[a]=tim,diss[a]=curs.count(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=sqrt(n/log2(n));
  for(I i=n-1;i>=0;i--)dfs1(i);
  while(q--){
    I t,y;cin>>t>>y,t--;
    curs.clear();
    for(I i=0;i<y;i++){I c;cin>>c,curs.insert(c-1);}
    I res=MIN;
    for(auto[dis,i]:tops[t])if(!curs.count(i)){res=dis;break;}
    if(res!=MIN){printf("%i\n",res);continue;}
    if(curs.size()<siz){printf("-1\n");continue;}
    printf("%i\n",dfs2(t)==MIN?-1:diss[t]),tim++;
  }
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs1(I)':
bitaro.cpp:29: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]
   29 |   while(tops[a].size()<siz){
      |         ~~~~~~~~~~~~~~^~~~
bitaro.cpp:34: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]
   34 |     if(i+1<tops[x].size()){
      |        ~~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'I main()':
bitaro.cpp:62:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'I' {aka 'int'} [-Wsign-compare]
   62 |     if(curs.size()<siz){printf("-1\n");continue;}
      |        ~~~~~~~~~~~^~~~

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