week13- D. Become an Escapiest is not easy!, Author Solution

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strD(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const LL INF = 2e18;
const int SIZE = 1e7+10;
int N,M;
LL E,x[100010];
int d[40],ban[SIZE],D,tt;
struct Union_Find{
    int d[200],num[200];
    void init(int n){
        REP(i,n)d[i]=i,num[i]=1;
    }
    int find(int x){
        return (x!=d[x])?(d[x]=find(d[x])):x;
    }
    bool uu(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return 0;
        if(num[x]>num[y])swap(x,y);
        num[y]+=num[x];
        d[x]=y;
        return 1;
    }
}U;
int bfs[SIZE];
bool valid(int ed){
    int rr=0;
    REP(i,D){
        bfs[rr++]=i;
        ban[i]=tt;
    }
    REP(i,rr){
        int x=bfs[i];
        REP(j,N){
            if(x+d[j]>ed)return 1;
            if(ban[x+d[j]]!=tt){
                ban[x+d[j]]=tt;
                bfs[rr++]=x+d[j];
            }
            if(x>=d[j]&&ban[x-d[j]]!=tt){
                ban[x-d[j]]=tt;
                bfs[rr++]=x-d[j];
            }
        }
    }
    return 0;
}
int main(){
    CASET{
        RII(N,M);
        scanf("%I64d",&E);
        REP(i,N)RI(d[i]);
        sort(d,d+N);
        int gg=d[0];
        REPP(i,1,N)gg=__gcd(gg,d[i]);
        REP(i,N)d[i]/=gg;
        REP(i,M){
            scanf("%I64d",&x[i]);
            if(x[i]%gg){
                i--;M--;
            }
            else x[i]/=gg;
        }
        if(E%gg){
            puts("evading is impossible");
            continue;
        }
        E/=gg;
        if(!M){
            puts("evadable");
            continue;
        }
        U.init(100);
        REPP(i,d[0],100){
            REP(j,N){
                if(i>=d[j])U.uu(i,i-d[j]);
            }
            if(U.num[U.find(i)]==i+1){
                D=i+1;
                break;
            }
        }
        D=max(D,d[N-1]+1);
        sort(x,x+M);
        bool fail=0;
        for(int i=0,j;i<M;){
            LL low=x[i]-D;
            tt++;
            for(j=i;j+1<M&&x[j]+D>=x[j+1];j++);
            for(;i<=j;i++)ban[x[i]-low]=tt;
            if(!valid(x[j]-low)){
                fail=1;
                break;
            }
        }
        puts(fail?"evading is impossible":"evadable");
    }
    return 0;
}