The 2014 ACM-ICPC Asia Mudanjiang Regional First Round小記
4648 ワード
C
J
struct Edge{
int v ;
int next ;
}e[400008] ;
int g[100008] ;
bool is[100008] ;
int id ;
int a[100008] ;
int vis[100008] ;
bool can[100008] ;
inline void add(int u , int v){
e[id].v = v ;
e[id].next = g[u] ;
g[u] = id++ ;
}
int father[100008] ;
int gf(int x){
if(x == father[x]) return x ;
else return father[x] = gf(father[x]) ;
}
int n , m , k , L ;
inline void meg(int x , int y){
int fx = gf(x) ;
int fy = gf(y) ;
if(fx != fy) father[fx] = fy ;
}
void dfs(int u , int idx){
//printf("%d->" , u) ;
vis[u] = 1 ;
for(int i = g[u] ; i != -1 ; i = e[i].next){
int v = e[i].v ;
if(vis[v] || is[v]){
meg(v , a[idx]) ;
continue ;
}
if(is[v] && !vis[v]) continue ;
meg(v , a[idx]) ;
dfs(v , idx) ;
}
}
int main(){
int t , x , u , v , i ;
cin>>t ;
while(t--){
scanf("%d%d%d" , &n , &m ,&k) ;
fill(g , g+n+1 , -1) ;
fill(is , is+n+1 , 0) ;
id = 0 ;
for(i = 1 ; i <= k ; i++){
scanf("%d" , &x) ;
is[x] = 1 ;
}
while(m--){
scanf("%d%d" , &u ,&v) ;
add(u , v);
add(v , u) ;
}
for(i = 1 ; i <= n ; i++) father[i] = i ;
scanf("%d" , &L) ;
for(i = 1 ; i <= L ; i++) scanf("%d" , &a[i]) ;
fill(vis , vis+1+n , 0) ;
dfs(a[1] , 1) ;
for(i = 2 ; i <= L ; i++){
if(gf(a[i-1]) == gf(a[i])) dfs(a[i] , i) ;
else break ;
}
int yes = 1 ;
for(i = 1 ; i <= n ; i++){
if(!vis[i]){
yes = 0 ;
break ;
}
}
if(yes) puts("Yes") ;
else puts("No") ;
}
return 0 ;
}
J
string s ;
int ok1(int len){
string ab = "" ;
string ab2 = "" ;
string a = "" ;
string b = "" ;
int i ;
for(i = 0 ; i < len ; i++) ab += s[i] ;
for(i = len ; i < s.length() && i < 2*len ; i++) ab2 += s[i] ;
if(ab != ab2) return 0 ;
for(i = 2*len ; i < s.length() ; i++) a += s[i] ;
if(a == "") return 0 ;
if(a.length() >= ab.length()) return 0 ;
string a2 = ab.substr(0 , a.length()) ;
if(a != a2) return 0 ;
b = ab.substr(a.length()) ;
if(a != b) return 1 ;
return 0 ;
}
int ok2(int len){
string ab = "" ;
string ab2 = "" ;
string ab3 = "" ;
string c = "" ;
int i ;
for(i = 0 ; i < len ; i++) ab += s[i] ;
for(i = len ; i < s.length() && i < 2*len ; i++) ab2 += s[i] ;
if(ab != ab2) return 0 ;
for(i = s.length() - len ; i < s.length() ; i++) ab3 += s[i] ;
if(ab != ab3) return 0 ;
if(2*len >= s.length() - len) return 0 ;
for(i = 2*len ; i < s.length() - len ; i++) c += s[i] ;
if(c == "") return 0 ;
string A , B ;
for(i = 0 ; i < ab.length() ; i++){
A = ab.substr(0 , i) ;
B = ab.substr(i) ;
if(A != "" && B != "" && A != B && A != c && B != c) return 1 ;
}
return 0 ;
}
char str[100] ;
int main(){
int t , i , yes ;
cin>>t ;
while(t--){
scanf("%s" , &str) ;
s = "" ;
for(i = 0 ; i < strlen(str) ; i++){
if( ('a' <= str[i] && str[i] <= 'z')
|| ('A' <= str[i] && str[i] <= 'Z') )
s += str[i] ;
}
yes = 0 ;
for(i = 2 ; i <= s.length()/2 ; i++){
if(ok1(i)){
yes = 1 ;
break ;
}
}
if(yes){
puts("Yes") ;
continue ;
}
for(i = 2 ; i <= s.length()/2 ; i++){
if(ok2(i)){
yes = 1 ;
break ;
}
}
if(yes){
puts("Yes") ;
continue ;
}
puts("No") ;
}
return 0;
}