제출 #204420

#제출 시각아이디문제언어결과실행 시간메모리
204420dolphingarlic다리 (APIO19_bridges)C++14
100 / 100
2451 ms29456 KiB
#include<bits/stdc++.h> #define FOR(i,x,y) for(int i=x;i<y;i++) using namespace std;const int B=1000,N=1e5+1;int n,m,q;stack<int>s;int z[N],c[N];void rs(){iota(c+1,c+1+n,1);fill(z+1,z+n+1,1);}inline int f(int a){while(c[a]!=a)a=c[a];return a;}void o(int a,int b){a=f(a),b=f(b);if(a == b)return;if(z[a]>z[b])swap(a,b);s.push(a);z[b]+=z[a];c[a]=c[b];}void rb(int x){while(s.size()>x){int k=s.top();s.pop();z[c[k]] -= z[k];c[k]=k;}}int u[N],v[N],w[N];int t[N],x[N],y[N];bool h[N];vector<int>to_join[B];int ans[N];int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>n>>m;FOR(i,1,m+1)cin>>u[i]>>v[i]>>w[i];cin>>q;FOR(i,1,q+1)cin>>t[i]>>x[i]>>y[i];for(int l=1;l<=q;l+=B){int r=min(q+1,l+B);rs();fill(h+1,h+m+1,false);vector<int>ask,upd,unh;FOR(i,l,r){if(t[i] == 1){h[x[i]]=true;upd.push_back(i);} else ask.push_back(i);}FOR(i,1,m+1)if(!h[i])unh.push_back(i);FOR(i,l,r){if(t[i] == 1)w[x[i]]=y[i];else {to_join[i - l].clear();for(int j:upd)if(w[x[j]] >= y[i])to_join[i - l].push_back(x[j]);}}sort(ask.begin(),ask.end(),[&](int a,int b){ return y[a]>y[b];});sort(unh.begin(),unh.end(),[&](int a,int b){ return w[a]>w[b];});int ptr=0;for(int i:ask){while(ptr<unh.size()&& w[unh[ptr]] >= y[i]){o(u[unh[ptr]],v[unh[ptr]]);ptr++;}int p=s.size();for(int j:to_join[i - l])o(u[j],v[j]);ans[i]=z[f(x[i])];rb(p);}}FOR(i,1,q+1)if(t[i] == 2)cout<<ans[i]<<'\n';return 0;}

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

bridges.cpp: In function 'void rb(int)':
bridges.cpp:3:315: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 using namespace std;const int B=1000,N=1e5+1;int n,m,q;stack<int>s;int z[N],c[N];void rs(){iota(c+1,c+1+n,1);fill(z+1,z+n+1,1);}inline int f(int a){while(c[a]!=a)a=c[a];return a;}void o(int a,int b){a=f(a),b=f(b);if(a == b)return;if(z[a]>z[b])swap(a,b);s.push(a);z[b]+=z[a];c[a]=c[b];}void rb(int x){while(s.size()>x){int k=s.top();s.pop();z[c[k]] -= z[k];c[k]=k;}}int u[N],v[N],w[N];int t[N],x[N],y[N];bool h[N];vector<int>to_join[B];int ans[N];int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>n>>m;FOR(i,1,m+1)cin>>u[i]>>v[i]>>w[i];cin>>q;FOR(i,1,q+1)cin>>t[i]>>x[i]>>y[i];for(int l=1;l<=q;l+=B){int r=min(q+1,l+B);rs();fill(h+1,h+m+1,false);vector<int>ask,upd,unh;FOR(i,l,r){if(t[i] == 1){h[x[i]]=true;upd.push_back(i);} else ask.push_back(i);}FOR(i,1,m+1)if(!h[i])unh.push_back(i);FOR(i,l,r){if(t[i] == 1)w[x[i]]=y[i];else {to_join[i - l].clear();for(int j:upd)if(w[x[j]] >= y[i])to_join[i - l].push_back(x[j]);}}sort(ask.begin(),ask.end(),[&](int a,int b){ return y[a]>y[b];});sort(unh.begin(),unh.end(),[&](int a,int b){ return w[a]>w[b];});int ptr=0;for(int i:ask){while(ptr<unh.size()&& w[unh[ptr]] >= y[i]){o(u[unh[ptr]],v[unh[ptr]]);ptr++;}int p=s.size();for(int j:to_join[i - l])o(u[j],v[j]);ans[i]=z[f(x[i])];rb(p);}}FOR(i,1,q+1)if(t[i] == 2)cout<<ans[i]<<'\n';return 0;}
                                                                                                                                                                                                                                                                                                                   ~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:3:1089: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 using namespace std;const int B=1000,N=1e5+1;int n,m,q;stack<int>s;int z[N],c[N];void rs(){iota(c+1,c+1+n,1);fill(z+1,z+n+1,1);}inline int f(int a){while(c[a]!=a)a=c[a];return a;}void o(int a,int b){a=f(a),b=f(b);if(a == b)return;if(z[a]>z[b])swap(a,b);s.push(a);z[b]+=z[a];c[a]=c[b];}void rb(int x){while(s.size()>x){int k=s.top();s.pop();z[c[k]] -= z[k];c[k]=k;}}int u[N],v[N],w[N];int t[N],x[N],y[N];bool h[N];vector<int>to_join[B];int ans[N];int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>n>>m;FOR(i,1,m+1)cin>>u[i]>>v[i]>>w[i];cin>>q;FOR(i,1,q+1)cin>>t[i]>>x[i]>>y[i];for(int l=1;l<=q;l+=B){int r=min(q+1,l+B);rs();fill(h+1,h+m+1,false);vector<int>ask,upd,unh;FOR(i,l,r){if(t[i] == 1){h[x[i]]=true;upd.push_back(i);} else ask.push_back(i);}FOR(i,1,m+1)if(!h[i])unh.push_back(i);FOR(i,l,r){if(t[i] == 1)w[x[i]]=y[i];else {to_join[i - l].clear();for(int j:upd)if(w[x[j]] >= y[i])to_join[i - l].push_back(x[j]);}}sort(ask.begin(),ask.end(),[&](int a,int b){ return y[a]>y[b];});sort(unh.begin(),unh.end(),[&](int a,int b){ return w[a]>w[b];});int ptr=0;for(int i:ask){while(ptr<unh.size()&& w[unh[ptr]] >= y[i]){o(u[unh[ptr]],v[unh[ptr]]);ptr++;}int p=s.size();for(int j:to_join[i - l])o(u[j],v[j]);ans[i]=z[f(x[i])];rb(p);}}FOR(i,1,q+1)if(t[i] == 2)cout<<ans[i]<<'\n';return 0;}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              ~~~^~~~~~~~~~~
#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...