제출 #208187

#제출 시각아이디문제언어결과실행 시간메모리
208187Segtree다리 (APIO19_bridges)C++14
14 / 100
2400 ms19328 KiB
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<set> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<ll,ll> P; #define rep(i,n) for(int i=0;i<n;i++) #define chmin(a,b) a=min(a,b) #define chmax(a,b) a=max(a,b) #define all(x) x.begin(),x.end() #define B 800 #define N 50010 #define M 100010 namespace uf{ ll dat[N]; stack<P> s; void init(){ rep(i,N)dat[i]=-1; while(!s.empty())s.pop(); } void confirm(){ while(!s.empty())s.pop(); } ll find(ll x){ return (dat[x]<0?x:find(dat[x])); } ll siz(ll x){ return -dat[find(x)]; } void unite(ll a,ll b){ a=find(a),b=find(b); if(a==b)return; if(-dat[a]<-dat[b])swap(a,b); s.push(make_pair(a,dat[a])); s.push(make_pair(b,dat[b])); dat[a]+=dat[b]; dat[b]=a; } void rollback(){ while(!s.empty()){ dat[s.top().first]=s.top().second; s.pop(); } } }; typedef struct qry{ ll s,w,id; bool operator<(const qry&key)const{ return this->w>key.w; } }qry;//t=2のクエリの構造体 int n,m,q; int a[M],b[M],c[M]; int t[M],x[M],y[M]; int fans[M]; int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]>>b[i]>>c[i]; } cin>>q; rep(i,q){ cin>>t[i]>>x[i]>>y[i]; } for(int L=0;L<q;L+=B){ int R=min(q,L+B); bool used[N]; for(int i=1;i<=m;i++)used[i]=0; for(int i=L;i<R;i++){ if(t[i]==1)used[x[i]]=1; } vector<ll> S;//このクエリバケット内で変更がある辺のid vector<P> E;//変更のない辺{コスト,id}、降順にuniteしていく for(int i=1;i<=m;i++){ if(used[i])S.push_back(i); else E.push_back(make_pair(c[i],i)); } sort(all(E)); vector<qry> Q;//バケット内のクエリ、wの降順に答えていく for(int i=L;i<R;i++){ if(t[i]==2){ Q.push_back((qry){x[i],y[i],i}); } } sort(all(Q)); uf::init(); ll cc[B][B];//cc[i][j]:=辺S[j]のクエリL+iの直前のコスト for(int i=0;i<S.size();i++){ cc[0][i]=c[S[i]]; } for(int i=L;i<R;i++){ rep(j,S.size())cc[i-L+1][j]=cc[i-L][j]; if(t[i]==1){ cc[i-L+1][lower_bound(all(S),x[i])-S.begin()]=y[i]; } } for(auto qs:Q){ while(E.size()>0&&E.back().first>=qs.w){ ll id=E.back().second; uf::unite(a[id],b[id]); E.pop_back(); } uf::confirm(); for(int i=0;i<S.size();i++){ if(cc[qs.id-L][i]>=qs.w){ uf::unite(a[S[i]],b[S[i]]); } } fans[qs.id]=uf::siz(qs.s); uf::rollback(); } for(int i=L;i<R;i++){ if(t[i]==1)c[x[i]]=y[i]; } } for(int i=0;i<q;i++)if(t[i]==2)cout<<fans[i]<<"\n"; }

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

bridges.cpp: In function 'int main()':
bridges.cpp:93:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<S.size();i++){
               ~^~~~~~~~~
bridges.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
bridges.cpp:97:8:
    rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
        ~~~~~~~~~~              
bridges.cpp:97:4: note: in expansion of macro 'rep'
    rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
    ^~~
bridges.cpp:109:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<S.size();i++){
                ~^~~~~~~~~
#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...