제출 #281721

#제출 시각아이디문제언어결과실행 시간메모리
281721groeneprof다리 (APIO19_bridges)C++14
14 / 100
692 ms24032 KiB
#include <bits/stdc++.h> #define P(a) do{if(debug) cout<<a<<endl;} while(false) #define H(a) P(#a<<": "<<a) #define FR(i,a,b) for(int i = (a); i<(b); i++) #define F(i,n) FR(i,0,n) const bool debug = 0; const int inf = 2e9; using namespace std; vector<vector<int> > ts, par, siz; vector<pair<int,int> > edges; vector<int> weights; int n, m, q; int root(int a,int t){ if(par[a].back() == a){ return a; } if(ts[a].back() > t){ ts[a].push_back(t); par[a].push_back(par[a].back()); siz[a].push_back(siz[a].back()); } return par[a].back() = root(par[a].back(),t); } void merge(int a, int b, int t){ P("a"); if(rand()%2) swap(a,b); int ra = root(a,t), rb = root(b,t); if(ra==rb) return; if(ts[ra].back()>t){ ts[ra].push_back(t); par[ra].push_back(par[ra].back()); siz[ra].push_back(siz[ra].back()); } if(ts[rb].back()>t){ ts[rb].push_back(t); par[rb].push_back(par[rb].back()); siz[rb].push_back(siz[rb].back()); } par[rb].back() = ra; siz[ra].back() += siz[rb].back(); } void generate(){ siz.resize(n,{1}); par.resize(n,{0}); ts.resize(n,{inf}); F(i,n){ par[i][0] = i; } vector<pair<int,pair<int,int> > > sorted(m); F(i, m){ sorted[i] = make_pair(weights[i],edges[i]); } sort(sorted.rbegin(), sorted.rend()); for(auto e : sorted){ merge(e.second.first, e.second.second, e.first); /*F(i,n){ cout<<i<<": "; F(j,par[i].size()){ cout<<"{"<<par[i][j]<<","<<siz[i][j]<<","<<ts[i][j]<<"} "; } cout<<endl; }*/ } /*F(i,n){ cout<<i<<": "; F(j,par[i].size()){ cout<<"{"<<par[i][j]<<","<<siz[i][j]<<","<<ts[i][j]<<"} "; } cout<<endl; }*/ } int root2(int a, int t){ int i = 0; for(int bit = 1<<20; bit>0; bit/=2){ if(i+bit<ts[a].size() && ts[a][i+bit] >= t){ i+=bit; } } if(par[a][i] == a) return a; return root2(par[a][i],t); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; edges.resize(m); weights.resize(m); F(i,m){ cin>>edges[i].first>>edges[i].second>>weights[i]; edges[i].first--; edges[i].second--; } generate(); cin>>q; F(i,q){ int type; cin>>type; if(type==1){ } else{ int a, t; cin>>a>>t; a--; int ra = root2(a,t); H(ra); int id = 0; for(int bit = 1<<20; bit>0; bit/=2){ if(id+bit<ts[ra].size() && ts[ra][id+bit] >= t){ id+=bit; } } cout<<siz[ra][id]<<endl; } } return 0; }

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

bridges.cpp: In function 'int root2(int, int)':
bridges.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   if(i+bit<ts[a].size() && ts[a][i+bit] >= t){
      |      ~~~~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     if(id+bit<ts[ra].size() && ts[ra][id+bit] >= t){
      |        ~~~~~~^~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...