제출 #208192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208192		Segtree	다리 (APIO19_bridges)	C++14	100 / 100	2937 ms	16472 KiB

bridges

#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];
ll cc[B+1][B];
bool used[N];

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);
		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();
		//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:94: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:98:8:
    rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
        ~~~~~~~~~~              
bridges.cpp:98:4: note: in expansion of macro 'rep'
    rep(j,S.size())cc[i-L+1][j]=cc[i-L][j];
    ^~~
bridges.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<S.size();i++){
                ~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27