记忆化搜索+拓扑排序

处理输入端的时候，可以将每个输入端看成一个编号大于n的结点，dfs搜到编号大于n的结点时，去找对应的input的状态即可。
在官网提交的时候，没加记忆化，直接踩着线过，刚好1.0s，在acwing上提交，第7个点就T了。加了记忆化后效果显著，直接变成31ms(官网)

C++ 代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;

int T,s,m,n,k;
vector<int>edges[501],redges[501];
vector<int>input[10001];
vector<int>query[10001];
int output[10001][501];
int indeg[501];
string type[501],str;

void initial(){
    for(int i=0;i<=500;i++){
        edges[i].clear();
        redges[i].clear();
        type[i].clear();
    }
    for(int i=0;i<=10000;i++){
        input[i].clear();
        query[i].clear();
    }
    memset(indeg,0,sizeof indeg);
    memset(output,-1,sizeof output);
}

int dfs(int now,int seq){
    if(now>n) return input[seq][now-n-1];
    if(output[seq][now]>=0) return output[seq][now];//记忆化搜索，当这个状态已搜过时，直接返回结果即可
    int res;
    if(type[now]=="NOT"){
        res=!dfs(redges[now][0],seq);
    }
    else if(type[now]=="AND"){
        res=1;
        for(int i=0;i<redges[now].size();i++){
            int t=redges[now][i];
            res=res&&dfs(t,seq);
        }
    }
    else if(type[now]=="OR"){
        res=0;
        for(int i=0;i<redges[now].size();i++){
            int t=redges[now][i];
            res=res||dfs(t,seq);
        }
    }
    else if(type[now]=="XOR"){
        res=0;
        for(int i=0;i<redges[now].size();i++){
            int t=redges[now][i];
            res=res^dfs(t,seq);
        }
    }
    else if(type[now]=="NAND"){
        res=1;
        for(int i=0;i<redges[now].size();i++){
            int t=redges[now][i];
            res=res&&dfs(t,seq);
        }
        res=!res;
    }
    else{
        res=0;
        for(int i=0;i<redges[now].size();i++){
            int t=redges[now][i];
            res=res||dfs(t,seq);
        }
        res=!res;
    }
    return output[seq][now]=res;
}

bool toposort(){
    queue<int>nodes;
    for(int i=1;i<=n;i++){
        if(indeg[i]==0) nodes.push(i);
    }
    while(!nodes.empty()){
        int temp=nodes.front();
        nodes.pop();
        for(int i=0;i<edges[temp].size();i++){
            int t=edges[temp][i];
            indeg[t]--;
            if(indeg[t]==0) nodes.push(t);
        }
    }
    for(int i=1;i<=n;i++){
        if(indeg[i]!=0) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>T;
    while(T--){
        initial();
        cin>>m>>n;
        for(int i=1;i<=n;i++){
            cin>>type[i]>>k;
            for(int t=0;t<k;t++){
                cin>>str;
                char tp=str[0];
                int num=0;
                for(int j=1;j<str.size();j++){
                    num=num*10+str[j]-'0';
                }
                if(tp=='O'){
                    edges[num].push_back(i);
                    redges[i].push_back(num);
                    indeg[i]++;
                }
                else if(tp=='I'){
                    redges[i].push_back(n+num);
                }
            }
        }
        cin>>s;
        for(int i=1;i<=s;i++){
            for(int t=1;t<=m;t++){
                int x;
                cin>>x;
                input[i].push_back(x);
            }
        }
        for(int i=1;i<=s;i++){
            int a,b;
            cin>>a;
            for(int t=1;t<=a;t++){
                cin>>b;
                query[i].push_back(b);
            }
        }

        if(toposort()==false){
            cout<<"LOOP"<<endl;
            continue;
        }

        for(int i=1;i<=s;i++){
            for(int t=0;t<query[i].size();t++){
                cout<<dfs(query[i][t],i)<<" ";
            }
            cout<<endl;
        }
    }

    return 0;
}