QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#787477 | #9551. The Emperor | liuyz11 | WA | 4ms | 23352kb | C++14 | 1.9kb | 2024-11-27 12:06:22 | 2024-11-27 12:06:23 |
Judging History
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())
#define int long long
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);
}
signed main(){
int n;
scanf("%lld", &n);
getchar();
rep(i, 1, n){
char ch = getchar();
if(ch == 'P'){
f[i] = 1;
scanf("OP %lld GOTO %lld; PUSH %lld GOTO %lld", &g[i].a, &g[i].b, &g[i].c, &g[i].d);
}
else{
f[i] = 0;
scanf("ALT; PUSH %lld GOTO %lld", &g[i].c, &g[i].d);
}
getchar();
}
// rep(i, 1, n){
// printf("%lld : %lld %lld %lld %lld\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("%lld %lld %lld %lld\n", i, j, dp[i][j].fi, dp[i][j].se);
// }
pii ans = dfs(1, 0);
if(ans.se == -1) puts("-1");
else printf("%lld\n", ans.fi);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 23036kb
input:
1 HALT; PUSH 1 GOTO 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 22948kb
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: 23352kb
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: 22908kb
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'