QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #796407 | #8313. Nim Cheater | eggegg185 | WA | 1ms | 6748kb | C++14 | 1.3kb | 2024-12-01 18:14:23 | 2024-12-01 18:14:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
vector<int> vec[20010]; int a[40010],b[40010],req[40010],ans[40010],siz[40010],son[40010],sum,fa[40005];
void D(int now) {
siz[now] = 1; for(auto v:vec[now]) {
D(v); siz[now] += siz[v];
if(!son[now] || siz[son[now]]<siz[v]) son[now] = v;
}
}
long long dp[18][17005],tmp[17005]; //sigh
void dfs(int now,int dep) {
if(dep >= 18) exit(0);
sum ^= a[now]; ans[now] = dp[dep][sum];
for(auto v:vec[now]) {
if(v == son[now]) continue;
for(int i = 0; i < 16384; i++) {
//if((i^a[v]) >= 16384) exit(0);
dp[dep+1][i] = min(dp[dep][i],dp[dep][i^a[v]]+b[v]);
}
dfs(v,dep+1);
} if(son[now]) {
for(int i = 0; i < 16384; i++) tmp[i] = dp[dep][i];
for(int i = 0; i < 16384; i++) {
//if((i^a[son[now]]) >= 16384) exit(0);
dp[dep][i] = min(tmp[i],tmp[i^a[son[now]]]+b[son[now]]);
}
dfs(son[now],dep);
} sum ^= a[now];
}
char s[10];
signed main() {
int n,cnt = 0,cur = 0; scanf("%d",&n); for(int i = 1; i <= n; i++) {
scanf("%s",s+1);
if(s[1] == 'A') {cnt++; scanf("%d%d",&a[cnt],&b[cnt]); vec[fa[cnt] = cur].push_back(cnt); cur = cnt;}
else cur = fa[cur]; req[i] = cur;
} memset(dp,0x3f,sizeof(dp)); dp[0][0] = 0; dfs(0,0); for(int i = 1; i <= n; i++) printf("%d\n",ans[req[i]]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6748kb
input:
7 ADD 3 10 ADD 2 4 ADD 1 5 ADD 2 1 DEL DEL ADD 3 5
output:
10 14 0 1 0 14 4
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 6704kb
input:
1964 ADD 3004 35344 ADD 6315 69182 ADD 59 78550 ADD 13842 11063 ADD 6255 35962 DEL ADD 13953 33214 ADD 5693 55297 ADD 1056 32685 ADD 13524 45844 ADD 5495 63087 ADD 2963 5957 ADD 7390 51487 ADD 9194 77728 DEL ADD 1958 85909 DEL ADD 6060 26702 ADD 13745 1556 ADD 6128 21684 ADD 9177 98957 ADD 670 35242...
output:
result:
wrong answer 1st lines differ - expected: '35344', found: ''