QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#785464 | #9551. The Emperor | wlh | TL | 0ms | 3724kb | C++17 | 4.2kb | 2024-11-26 18:01:27 | 2024-11-26 18:01:28 |
Judging History
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...