QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785464#9551. The EmperorwlhTL 0ms3724kbC++174.2kb2024-11-26 18:01:272024-11-26 18:01:28

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 18:01:28]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3724kb
  • [2024-11-26 18:01:27]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1024 + 10, inf = 1e9, mod = 998244353;

struct nb{
    int f, a, x, b, y;
}vt[N];

stack<int>st;
struct node{
    int cnt, v, b;
}dp[N][N];

int sum = 0;


void dfs(int u, int t) {
    if(dp[u][(int)st.top()].cnt) return ;
    sum ++;
    if(sum >= 1024 * 1024 + 1024) {
        while(st.size()){
            st.pop();
        }
        return ;
    }
    if(vt[u].f == 1){
        int a = vt[u].a;
        if(st.size() && st.top() == vt[u].a){
            st.pop();
            // cout << "333 " << ' ' << u << ' ' << a << ' ' << vt[u].x << ' ' << (int)st.size() << ' ' << (int)st.top() << endl; 
            dp[u][a] = {1, vt[u].x, st.top()};
            return ;
        }
        else{
            int b = vt[u].b;
            int tp = st.top(), sz = st.size();
            st.push(b);
            // cout << "b : " << b << ' ' << tp << endl;
            int y = vt[u].y, v = y;
            dp[u][tp].cnt = 1;
            dp[u][tp].b = tp;
            while((int)st.size() >= sz){
                dfs(v, t + 1);
                // cout << "111 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;
                
                int cnt = dp[v][b].cnt;
                int vv = v, bb = b;
                v = dp[vv][bb].v;
                b = dp[vv][bb].b;
                
                dp[u][tp].cnt = (dp[u][tp].cnt + cnt) % mod;

                dp[u][tp].v = v;
                dp[u][tp].b = b;

                // cout << "222 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;
                // cout << endl;
                
            }
            return ;
        }
    }
    else{
        if((int)st.size() == 1){
            st.pop();
            dp[u][0] = {1, 0, 0};
            return ;
        }
        else{
            int b = vt[u].b;
            int tp = st.top(), sz = st.size();
            st.push(b);
            // cout << "b : " << b << ' ' << tp << endl;
            int y = vt[u].y, v = y;
            dp[u][tp].cnt = 1;
            dp[u][tp].b = tp;
            while((int)st.size() >= sz){
                dfs(v, t + 1);
                // cout << "111 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;
                
                int cnt = dp[v][b].cnt;
                int vv = v, bb = b;
                v = dp[vv][bb].v;
                b = dp[vv][bb].b;
                
                dp[u][tp].cnt = (dp[u][tp].cnt + cnt) % mod;
                dp[u][tp].v = v;
                dp[u][tp].b = b;
                
                // cout << "222 " << u << ' ' << v << ' ' << b << ' ' << tp << ' ' << sz << ' ' << (int)st.size() << ' ' << dp[u][tp].cnt << endl;
                // cout << endl;
                
            }
            return ;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        char c;
        cin >> c;
        if(c == 'P'){
            vt[i].f = 1;
            scanf("OP %d GOTO %d; PUSH %d GOTO %d", &vt[i].a, &vt[i].x, &vt[i].b, &vt[i].y);
            if(n == 1){
                cout << -1 << endl;
                return ;
            }
        }
        else{
            vt[i].f = 2;
            scanf("ALT; PUSH %d GOTO %d", &vt[i].b, &vt[i].y);
        }
        // cout << vt[i].f << ' ' << vt[i].a << ' ' << vt[i].x << ' ' << vt[i].b << ' ' << vt[i].y << endl;
    }
    st.push(0);
    dfs(1, 0);

    // cout << dp[1][0].cnt << ' ' << dp[1][0].v << ' ' << dp[1][0].b << endl;
    // cout << dp[2][1].cnt << ' ' << dp[2][1].v << ' ' << dp[2][1].b << endl;
    // cout << dp[3][1].cnt << ' ' << dp[3][1].v << ' ' << dp[3][1].b << endl;
    
    if(sum == 1024 * 1024 + 1024){
        cout << -1 << endl;
    }
    else{
        cout << dp[1][0].cnt << endl;
    }
    // cout << sum << endl;
}

signed main() {
    // std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3724kb

input:

1
HALT; PUSH 1 GOTO 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

5
POP 1 GOTO 2; PUSH 1 GOTO 2
HALT; PUSH 1 GOTO 3
POP 1 GOTO 4; PUSH 2 GOTO 4
POP 1 GOTO 2; PUSH 2 GOTO 4
HALT; PUSH 99 GOTO 4

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

1
POP 1 GOTO 1; PUSH 1 GOTO 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Time Limit Exceeded

input:

61
POP 62 GOTO 61; PUSH 30 GOTO 60
POP 1 GOTO 3; PUSH 62 GOTO 61
POP 2 GOTO 61; PUSH 62 GOTO 61
POP 4 GOTO 7; PUSH 2 GOTO 61
POP 62 GOTO 61; PUSH 3 GOTO 4
POP 62 GOTO 61; PUSH 3 GOTO 5
POP 5 GOTO 10; PUSH 3 GOTO 6
POP 62 GOTO 61; PUSH 4 GOTO 7
POP 62 GOTO 61; PUSH 4 GOTO 8
POP 6 GOTO 12; PUSH 4 GOTO...

output:


result: