kmjp's blog

競技プログラミング参加記です

Codeforces #673 Div1 D. Graph and Queries

コード量は多いけど何とか解けてよかった。
https://codeforces.com/contest/1416/problem/D

問題

N頂点M辺のグラフが与えられる。
各点には、異なる正整数が書かれている。

以下のクエリに答えよ。

  • 頂点vが指定されるので、vを含む連結成分内の頂点のうち、書かれた整数の最大値を答えよ。その後、その頂点の整数は0となる。
  • 辺が1つ指定されるので、その辺を削除せよ。

解法

まず、扱いやすくするためにグラフを木に変える。
辺が削除されるタイミングが遅い順にグラフに(連結成分が減るように)追加していき、全域木にしていこう。
その際、u-vを結ぶ辺を追加する場合、直接u-vを結ぶのではなく、(uを含む連結成分の代表点)-(新規代表点)-(vを含む連結成分の代表点)と、点を追加しながら行う。

また、全体を連結にするため、全辺の追加が終わったら、新規に根となる頂点を追加し、各連結成分の代表点をそこにつなげよう。
そうすると、この木は削除されるタイミングが早いものほど根に近くなる。
すなわち、前者のクエリの対象の連結成分は、常にあるサブツリー全体となる。
あとはDFSで頂点を並べ替えると、整数の最大値を求めるクエリがRMQで処理できるようになる。

int N,M,Q;
int P[202020];
int U[303030],V[303030],T[303030];
int A[505050],B[505050];
int rep[1010101],rt[1010101];

vector<int> VE[1010101];
int par[1010101][20];
int id;
int Lid[1010101],Rid[1010101];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1010101> uf;

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=0;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return max(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<int,1<<20> st;

void dfs(int cur) {
	Lid[cur]=id++;
	FORR(e,VE[cur]) dfs(e);
	Rid[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&Q);
	MINUS(par);
	FOR(i,N) {
		scanf("%d",&P[i]);
		rep[i]=i;
		rt[i]=1000000;
	}
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		U[i]=x-1;
		V[i]=y-1;
		T[i]=500000+i;
	}
	FOR(i,Q) {
		scanf("%d%d",&A[i],&B[i]);
		B[i]--;
		if(A[i]==2) T[B[i]]=i;
	}
	int nex=N;
	vector<pair<int,int>> E;
	FOR(i,M) E.push_back({-T[i],i});
	sort(ALL(E));
	FORR(e,E) {
		x=uf[U[e.second]];
		y=uf[V[e.second]];
		if(x!=y) {
			VE[nex].push_back(rep[x]);
			VE[nex].push_back(rep[y]);
			par[rep[x]][0]=nex;
			par[rep[y]][0]=nex;
			rt[nex]=-e.first;
			rep[x]=rep[y]=nex++;
			uf(x,y);
		}
	}
	
	
	FOR(i,nex) {
		if(par[i][0]==-1) {
			par[i][0]=nex;
			VE[nex].push_back(i);
		}
	}
	par[nex][0]=nex;
	rt[nex]=-1;
	nex++;
	FOR(j,19) {
		FOR(i,nex) {
			par[i][j+1]=par[par[i][j]][j];
		}
	}
	
	dfs(nex-1);
	FOR(i,N) st.update(Lid[i],P[i]);
	FOR(i,Q) {
		if(A[i]==1) {
			int cur=B[i];
			for(j=19;j>=0;j--) if(rt[par[cur][j]]>=i) cur=par[cur][j];
			auto a=st.getval(Lid[cur],Rid[cur]);
			//cout<<"!"<<i<<" "<<B[i]<<" "<<cur<<" "<<Lid[cur]<<" "<<Rid[cur]<<"     "<<a.first<<":"<<a.second<<endl;
			_P("%d\n",a.first);
			st.update(a.second,0);
			
		}
	}
}

まとめ

連結順に頂点を追加して全域木を作るテク、ちょくちょく使えそう。