QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210495#6331. Jewel Gameucup-team870WA 4ms4656kbC++143.1kb2023-10-11 15:18:112023-10-11 15:18:12

Judging History

你现在查看的是最新测评结果

  • [2023-10-11 15:18:12]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:4656kb
  • [2023-10-11 15:18:11]
  • 提交

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'