Codeforces ECR #105 : E. A-Z Graph

実装は軽め。
https://codeforces.com/contest/1494/problem/E

問題

N頂点の有向グラフを考える。
以下のクエリに順次答えよ。

• 指定された2頂点間に、指定された1文字をラベルとして持つ有向辺を追加する。
• 指定された2頂点間にある有向辺を削除する。
• 以下を満たす長さkのパスの存在の有無を答えよ。なお、パス上で同じ頂点を複数回通ってもよい。
  • パス上の頂点の並びに対し、逆向きにするようなパスも存在する。
  • 加えて、いずれの並びでも通った辺のラベルを並べて作る文字列が一緒である。

解法

パスの条件を考えると、結局2点を往復するパスだけ考えればよい。

• もし両方向同じラベルを持つ頂点対が1個でも存在すれば、条件を満たすパスは存在する。
• そうでない場合、両方向異なるラベルを持つ頂点対が1個でも存在すれば、kが奇数なら条件を満たすパスは存在する。

int N,M;
map<int,int> E[202020];
int N1,N2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	while(M--) {
		cin>>s;
		if(s=="+") {
			cin>>x>>y>>s;
			r=s[0]-'a'+1;
			E[x][y]=r;
			k=E[y][x];
			if(k==r) {
				N1++;
			}
			else if(k>0) {
				N2++;
			}
			
		}
		else if(s=="-") {
			cin>>x>>y;
			
			r=E[x][y];
			k=E[y][x];
			if(r==k) {
				N1--;
			}
			else if(k>0) {
				N2--;
			}
			E[x][y]=0;
		}
		else {
			cin>>x;
			x--;
			
			if(N1) {
				cout<<"YES"<<endl;
			}
			else if(x%2==0&&N2) {
				cout<<"YES"<<endl;
			}
			else {
				cout<<"NO"<<endl;
			}
		}
	}
}

まとめ

ECRの5問目にしては簡単？