Name the Crossing (AOJ1134)
ほんとに面白く無いんで読まないでいいです カレンダーを埋める用の記事.
本質はクエリ部分の入力としてそもそも存在しない通りの名前が来ることです.
あとはやるだけ(よく見ると通りは200個しかないと書いてあるのでsccすらいらない)
これカレンダーとしての意味皆無だな・・・(Advent Calendarと銘打って問題を解く口実にしたいだけなのはもはや明らか) できれば面白い問題を解きます.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; int N,M; map<string,int> mp; bool e[200][200],ee[200][200]; int t[200]; void dfs(int x,int c){ t[x]=c; rep(i,N){ if(e[x][i]&&t[i]==0) dfs(i,-c); else if(e[x][i]) assert(t[i]==-t[x]); } rep(i,N){ if(e[i][x]&&t[i]==0) dfs(i,-c); else if(e[i][x]) assert(t[i]==-t[x]); } } int main(){ while(true){ cin>>M; if(M==0) break; mp.clear(); rep(i,200) rep(j,200) e[i][j]=0,ee[i][j]=(i==j); rep(i,200) t[i]=0; int J=0; rep(i,M){ string st; cin>>st; int j=0; while(st[j]!='-') j++; string xx=st.substr(0,j),yy=st.substr(j+1); if(!mp.count(xx)) mp[xx]=J++; if(!mp.count(yy)) mp[yy]=J++; int x=mp[xx],y=mp[yy]; e[x][y]=1; } N=mp.size(); cout<<N<<endl; int I=1; rep(i,N) if(t[i]==0) dfs(i,I++); rep(i,N) rep(j,N){ bool a=0,b=1; rep(k,N){ if((e[i][k]||e[k][i])&&(e[j][k]||e[k][j])) a=1; if((e[i][k]&&e[k][j])||(e[j][k]&&e[k][i])) b=0; } if(a&&b) ee[i][j]=1; } rep(i,N) rep(j,N) e[i][j]|=ee[i][j]; rep(i,N) rep(j,N) rep(k,N) if(e[j][i]&&e[i][k]) e[j][k]=1; int Q; cin>>Q; rep(tt,Q){ string st; cin>>st; int j=0; while(st[j]!='-') j++; string xx=st.substr(0,j),yy=st.substr(j+1); if(!mp.count(xx)||!mp.count(yy)){ puts("NO"); continue; } int x=mp[xx],y=mp[yy]; if(t[x]==-t[y]&&e[x][y]) puts("YES"); else puts("NO"); } } }