제출 #821768

#제출 시각아이디문제언어결과실행 시간메모리
821768alvingogo열쇠 (IOI21_keys)C++17
100 / 100
664 ms55232 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") #define fs first #define sc second #define p_q priority_queue using namespace std; struct DSU{ vector<int> bo; void init(int n){ bo.resize(n); iota(bo.begin(),bo.end(),0); } int find(int x){ return bo[x]==x?x:bo[x]=find(bo[x]); } void merge(int x,int y){ bo[find(x)]=find(y); } }dsu; vector<int> r; vector<int> z,vis,ans,nxt,ret,dead; vector<int> lst; int sz=1e9; vector<vector<int> > to; vector<vector<pair<int,int> > > e; void bfs(int x,int s){ lst[x]=s; queue<int> q; q.push(x); while(q.size()){ auto h=q.front(); q.pop(); if(dsu.find(h)!=x){ dsu.merge(x,h); lst[dsu.find(h)]=s; for(auto y:nxt){ to[y].clear(); } nxt.clear(); for(auto h:ans){ z[r[h]]=0; } ans.clear(); return; } if(vis[h]){ continue; } vis[h]=1; ans.push_back(h); z[r[h]]=1; for(auto y:to[r[h]]){ q.push(y); } to[r[h]].clear(); for(auto y:e[h]){ if(z[y.fs]){ q.push(y.sc); } else{ to[y.fs].push_back(y.sc); nxt.push_back(y.fs); } } } dead[x]=1; if(ans.size()<sz){ ret=ans; sz=ans.size(); } else if(ans.size()==sz){ ret.insert(ret.end(),ans.begin(),ans.end()); } for(auto y:nxt){ to[y].clear(); } nxt.clear(); for(auto h:ans){ z[r[h]]=0; } ans.clear(); } vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) { int n=R.size(); int m=u.size(); dsu.init(n); e.resize(n); vis.resize(n); nxt.resize(n); lst.resize(n); z.resize(n); to.resize(n); dead.resize(n); r=R; for(int i=0;i<m;i++){ e[u[i]].push_back({c[i],v[i]}); e[v[i]].push_back({c[i],u[i]}); } for(int j=1;;j++){ int flag=0; fill(vis.begin(),vis.end(),0); for(int i=0;i<n;i++){ if(!dead[i] && dsu.find(i)==i && lst[i]!=j){ bfs(i,j); flag=1; } } if(flag==0){ break; } } vector<int> rr(n); for(auto h:ret){ rr[h]=1; } return rr; }

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

keys.cpp: In function 'void bfs(int, int)':
keys.cpp:68:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |  if(ans.size()<sz){
      |     ~~~~~~~~~~^~~
keys.cpp:72:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  else if(ans.size()==sz){
      |          ~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...