QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210495 | #6331. Jewel Game | ucup-team870 | WA | 4ms | 4656kb | C++14 | 3.1kb | 2023-10-11 15:18:11 | 2023-10-11 15:18:12 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 33;
vector<int> e[N], sta[N], b[N];
int pos[N], w[N], f[(1<<10)+2][33][33], id[N], du[N][N], vis[N][N];
P tmp[1025];
queue <P> q;
multiset<P> ksj;
int main() {
int n, m, A, B;
scanf("%d%d%d%d", &n, &m, &A, &B);
rep (i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
b[v].push_back(u);
}
int k; scanf("%d", &k);
rep (i, 1, k) {
scanf("%d%d", &pos[i], &w[i]);
id[pos[i]] = i;
}
int mx = (1<<k) - 1;
rep (s, 1, mx) {
sta[__builtin_popcount(s)].push_back(s);
}
rep (s, 1, mx) {
rep(i, 1, n) {
rep (j, 1, n) {
f[s][i][j] = -1e9;
}
}
}
rep (_, 1, k) {
for (auto s: sta[_]) {
auto g = f[s];
rep (i, 1, n) {
rep (j, 1, n) {
int top = 0;
for (auto v: e[i]) {
int p = id[v];
if ((s>>p-1) & 1) {
int t = s ^ (1<<p-1);
g[i][j] = max(g[i][j], -f[t][j][v] + w[p]);
tmp[++top] = P(-f[t][j][v] + w[p], i * n + j - 1);
} else {
du[i][j]++;
}
}
if (du[i][j] == 0) {
vis[i][j] = 1;
q.push(P(i, j));
} else {
while (top) ksj.insert(tmp[top--]);
}
}
}
while (1) {
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto v: b[j]) { //previous: (v, i)
if (vis[v][i]) continue;
du[v][i]--;
g[v][i] = max(g[v][i], -g[i][j]);
if (du[v][i] == 0) {
vis[v][i] = 1;
q.push(P(v, i));
} else {
ksj.insert(P(-g[i][j], v*n + i - 1));
}
}
}
if (ksj.empty()) break;
auto [v, t] = *ksj.rbegin();
ksj.erase(--ksj.end());
int i = t/n, j = t%n+1;
if (vis[i][j]) continue;
vis[i][j] = 1;
g[i][j] = v;
q.push(P(i, j));
}
rep (i, 1, n) {
rep (j, 1, n) {
if (!vis[i][j]) g[i][j] = 0;
vis[i][j] = du[i][j] = 0;
}
}
}
}
cout << f[mx][A][B];
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
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: 1ms
memory: 3824kb
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: 0ms
memory: 3568kb
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: 4656kb
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'