QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #313488 | #6331. Jewel Game | PlentyOfPenalty | WA | 4ms | 17528kb | C++20 | 3.9kb | 2024-01-24 19:53:58 | 2024-01-24 19:53:58 |
Judging History
answer
#include <bits/stdc++.h>
#define STATE [(1 << K) + 10][N + 10][N + 10]
#define all(x) begin(x), end(x)
using namespace std;
const int N = 30, K = 10;
const int INF = 1e9;
struct state {
int m, p, q, val;
} t;
int n, m, a, b, k, u, v, pos[K + 10], w[K + 10], id[N + 10];
int dp STATE, vis STATE, d STATE, mx;
vector<int> e[N + 10];
vector<state> ut STATE;
queue<state> q;
int main() {
#ifdef popteam
freopen("O.in", "r", stdin);
freopen("O.out", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> a >> b;
for (int i = 1; i <= m; ++i)
cin >> u >> v, e[u].push_back(v);
cin >> k;
for (int i = 1; i <= k; ++i) {
cin >> pos[i] >> w[i];
id[pos[i]] = i;
}
for (int i = 1; i < (1 << k); ++i) {
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) {
for (int t : e[j]) {
if (id[t] && ((i >> id[t] - 1) & 1)) {
ut[i - (1 << id[t] - 1)][k][t].push_back((state){i, j, k, w[id[t]]});
// cout << "(" << i << " " << j << " " << k << ")->(" << i - (1 << id[t] - 1) << " " << k << " " << t << ")\n";
++d[i][j][k];
} else {
ut[i][k][t].push_back((state){i, j, k, 0});
// cout << "(" << i << " " << j << " " << k << ")->(" << i << " " << k << " " << t << ")\n";
++d[i][j][k];
}
}
}
}
for (int i = 1; i < (1 << k); ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
dp[i][j][k] = -INF;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
vis[0][i][j] = 1, dp[0][i][j] = 0;
for (state x : ut[0][i][j]) {
--d[x.m][x.p][x.q], dp[x.m][x.p][x.q] = max(dp[x.m][x.p][x.q], x.val - dp[0][i][j]);
}
}
for (int i = 1; i < (1 << k); ++i) {
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
if (!d[i][j][k]) q.push((state){i, j, k});
while (1) {
while (!q.empty()) {
t = q.front(), q.pop();
vis[t.m][t.p][t.q] = 1;
// cout << "DP " << t.m << " " << t.p << " " << t.q << "=" << dp[t.m][t.p][t.q] << "\n";
for (state x : ut[t.m][t.p][t.q]) {
--d[x.m][x.p][x.q], dp[x.m][x.p][x.q] = max(dp[x.m][x.p][x.q], x.val - dp[t.m][t.p][t.q]);
if (x.m == i && !d[x.m][x.p][x.q]) q.push(x);
}
}
mx = 0;
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
if (!vis[i][j][k] && dp[i][j][k] > mx) {
mx = dp[i][j][k], t = (state){i, j, k};
}
if (mx > 0) {
vis[t.m][t.p][t.q] = 1;
// cout << "DP " << t.m << " " << t.p << " " << t.q << "=" << dp[t.m][t.p][t.q] << "\n";
for (state x : ut[t.m][t.p][t.q]) {
--d[x.m][x.p][x.q], dp[x.m][x.p][x.q] = max(dp[x.m][x.p][x.q], x.val - dp[t.m][t.p][t.q]);
if (x.m == i && !d[x.m][x.p][x.q]) q.push(x);
}
} else
break;
}
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
if (!vis[i][j][k]) {
vis[i][j][k] = 1, dp[i][j][k] = 0;
// cout << "DP " << i << " " << j << " " << k << "=0\n";
for (state x : ut[i][j][k]) {
--d[x.m][x.p][x.q], dp[x.m][x.p][x.q] = max(dp[x.m][x.p][x.q], x.val - dp[i][j][k]);
}
}
}
cout << dp[(1 << k) - 1][a][b] << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7936kb
input:
5 16 1 1 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 2 3 4 3 5 4 2 4 3 4 5 5 2 5 3 5 4 4 2 4 3 84 4 38 5 96
output:
46
result:
ok 1 number(s): "46"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8892kb
input:
8 16 8 4 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 1 5 2 6 3 7 4 8 5 1 6 2 7 3 8 4 6 1 29 2 34 3 41 5 7 6 26 7 94
output:
-23
result:
ok 1 number(s): "-23"
Test #3:
score: 0
Accepted
time: 3ms
memory: 7768kb
input:
5 5 2 1 1 1 2 3 3 4 4 5 5 2 2 4 1000000 5 100000
output:
1100000
result:
ok 1 number(s): "1100000"
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 17528kb
input:
10 20 1 2 1 4 1 7 2 2 2 4 3 6 3 3 4 8 4 7 5 7 5 1 6 9 6 2 7 9 7 3 8 8 8 6 9 7 9 8 10 10 10 2 8 3 92067840 4 2874502 5 36253165 6 70758738 7 4768969 8 16029185 9 16207515 10 44912151
output:
164899375
result:
wrong answer 1st numbers differ - expected: '132484345', found: '164899375'