QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787472#9551. The Emperorliuyz11WA 2ms14100kbC++141.8kb2024-11-27 12:03:562024-11-27 12:03:56

Judging History

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

  • [2024-11-27 12:03:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14100kb
  • [2024-11-27 12:03:56]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define repd(x, r, l) for(int x = r; x >= l; x--)
#define clr(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;
const int MAXN = 1105;

pii dp[MAXN][MAXN];
bool vis[MAXN][MAXN];
struct node{
    int a, b, c, d;
} g[MAXN];
int f[MAXN];

const int M = 1e7;

int cnt = 0;

pii dfs(int u, int a){
    cnt++;
    if(cnt > M) return mp(0, -1);
    if(!f[u] && !a) return mp(1, 0);
    if(f[u] && g[u].a == a) return mp(1, g[u].b);
    if(dp[u][a].fi != -1) return dp[u][a];
    if(vis[u][a]) return dp[u][a] = mp(0, -1);
    vis[u][a] = 1;
    pii res = dfs(g[u].d, g[u].c);
    if(res.se == -1) return dp[u][a] = mp(0, -1);
    if(!res.se) return dp[u][a] = mp(res.fi + 1, 0);
    pii res2 = dfs(res.se, a);
    vis[u][a] = 0;
    return dp[u][a] = mp(res.fi + res2.fi + 1, res2.se);
}

int main(){
    int n;
    scanf("%d", &n);
    getchar();
    rep(i, 1, n){
        char ch = getchar();
        if(ch == 'P'){
            f[i] = 1;
            scanf("OP %d GOTO %d; PUSH %d GOTO %d", &g[i].a, &g[i].b, &g[i].c, &g[i].d);
        }
        else{
            f[i] = 0;
            scanf("ALT; PUSH %d GOTO %d", &g[i].c, &g[i].d);
        }
        getchar();
    }
    // rep(i, 1, n){
    //     printf("%d : %d %d %d %d\n", f[i], g[i].a, g[i].b, g[i].c, g[i].d);
    // }
    clr(dp, -1);
    // rep(i, 1, n){
    //     rep(j, 1, n) printf("%d %d %d %d\n", i, j, dp[i][j].fi, dp[i][j].se);
    // }
    pii ans = dfs(1, 0);
    if(ans.se == -1) puts("-1");
    else printf("%d\n", ans.fi);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13428kb

input:

1
HALT; PUSH 1 GOTO 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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: 13656kb

input:

1
POP 1 GOTO 1; PUSH 1 GOTO 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 13444kb

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:

2147483647

result:

wrong answer 1st numbers differ - expected: '150994941', found: '2147483647'