AtCoder ARC #146 : D - >=<

問題名が記号なの、検索しにくそう。
https://atcoder.jp/contests/arc146/tasks/arc146_d

問題

整数N,MとK個の条件が与えられる。
1～Mの値を取るN要素の整数列Aのうち、以下のK個の条件をみたすものが存在するなら、その総和の最小値を求めよ。

• P,Q,X,Yが与えられる。A[P]とXの大小関係は、A[Q]とYの大小関係に一致しなければならない。

解法

大小関係は3種あるので、これを2種にする。

• A[P]≦X-1とA[Q]≦Y-1の真偽が等しい
• A[P]≦XとA[Q]≦Yの真偽が等しい

と2つの条件に分解すると、考える大小関係は小なりイコールの1つだけで良くなる。

ここから具体的にAを構築する。
A=(1,1,,,,,,)から始め、A[P]>Xとなっていたら、A[Q]=max(A[Q],Y+1)にする(またはP,XとQ,Yを逆にしたもの)という作業を変化がなくなるまで繰り返そう。

int N,M,K;
int P[404040],Q[404040],X[404040],Y[404040];
int A[404040];
vector<vector<int>> C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	int nex=0;
	FOR(i,K) {
		cin>>j>>x>>k>>y;
		C[j].push_back({x,k,y});
		C[k].push_back({y,j,x});
		C[j].push_back({x-1,k,y-1});
		C[k].push_back({y-1,j,x-1});
	}
	K=nex;
	queue<int> Q;
	for(i=1;i<=N;i++) {
		A[i]=1;
		Q.push(i);
		sort(ALL(C[i]));
		reverse(ALL(C[i]));
	}
	
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		if(A[cur]>M) {
			cout<<-1<<endl;
			return;
		}
		while(C[cur].size()&&A[cur]>C[cur].back()[0]) {
			x=C[cur].back()[1];
			y=C[cur].back()[2];
			C[cur].pop_back();
			A[x]=max(A[x],y+1);
			Q.push(x);
		}
	}
	ll ret=0;
	for(i=1;i<=N;i++) ret+=A[i];
	cout<<ret<<endl;
}

まとめ

言い換えに気が付けば簡単になるタイプの問題。