제출 #707449

#제출 시각아이디문제언어결과실행 시간메모리
707449EthanKim8683Bitaro’s Party (JOI18_bitaro)C++17
0 / 100
2069 ms4948 KiB
#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++; } }

컴파일 시 표준 에러 (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;}
      |        ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...