제출 #1114428

#제출 시각아이디문제언어결과실행 시간메모리
1114428kokoueBitaro’s Party (JOI18_bitaro)C++14
0 / 100
1 ms2640 KiB
#include<bits/stdc++.h> #define maxn 100010 #define f first #define s second using namespace std; int n,m,q; vector<int> edges[maxn]; bool blocked[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; if(a<b) swap(a,b); edges[a].push_back(b); } int B=100; vector<pair<int,int>> longest[n+1]; vector<int> dist(n+1,-1); for(int i=1;i<=n;i++) { // longest[i].push_back({0,i}); vector<int> from; vector<pair<int,int>> curr; curr.push_back({0,i}); for(auto e:edges[i]) { for(auto fff:longest[e]) { int way=fff.f; int ver=fff.s; if(dist[ver]==-1) { from.push_back(ver); dist[ver]=way+1; } else dist[ver]=max(dist[ver],way+1); } } for(auto e:from) curr.push_back({dist[e],e}); sort(curr.begin(),curr.end()); int idx=0; // printf("FOR size=%d %d: ",from.size(),i); while(idx<B && idx<curr.size()) { longest[i].push_back({curr[idx].f,curr[idx].s}); // printf("%d %d; ",curr[idx].f,curr[idx].s); idx++; } // printf("\n"); for(auto e:from) dist[e]=-1; from.clear(); curr.clear(); } for(int i=0;i<q;i++) { int start,y; cin>>start>>y; vector<int> c(y); for(int j=0;j<y;j++) { cin>>c[j]; blocked[c[j]]=1; } if(y>B) { vector<int> dp(start+1,-INT_MAX); dp[start]=0; int ans=0; for(int j=start;j>0;j--) { if(dp[j]==-INT_MAX) continue; if(!blocked[j]) ans=max(ans,dp[j]); for(auto e:edges[j]) dp[e]=max(dp[e],dp[j]+1); } cout<<ans<<"\n"; } if(y<=B) { for(int j=longest[start].size()-1;j>=0;j--) { if(!blocked[longest[start][j].s]) {cout<<longest[start][j].f<<"\n";break;} } } for(auto e:c) blocked[e]=0; } }

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'int main()':
bitaro.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(idx<B && idx<curr.size())
      |                        ~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...