QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212589#1972. JJ RallyZanite#WA 13ms11384kbC++173.7kb2023-10-13 17:43:212023-10-13 17:43:21

Judging History

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

  • [2023-10-13 17:43:21]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:11384kb
  • [2023-10-13 17:43:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using pii = pair<int, int>;

#define fi           first
#define se           second
#define All(x)       x.begin(), x.end()
#define debug(x)     cout << #x << " = " << (x) << '\n';
#define debugV(v, x) cout << #v << "[" << (x) << "] = " << v[x] << '\n';

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
    return os << "(" << p.fi << ", " << p.se << ")";
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
    os << "{"; bool osu = 1;
    for (auto i : v) {if (!osu) {os << ", ";} os << i; osu = 0;}
    return os << "}";
}

const int iINF = 1'000'000'000;
const ll INF   = 1'000'000'000'000'000'000;

const int maxN  = 24;
const int maxM  = 1 << 20;

int N, M, K;
vector<pii> adj[maxN];
int msk[2][maxM];
bool in[maxN];
int id[maxN];
int s[2], t[2];

void Dijkstra(int st, vector<int> &dist) {
    vector<bool> vis(N, false);
    priority_queue<pii, vector<pii>, greater<pii>> pyqe;
    pyqe.push({0, st});
    dist[st] = 0;
    while (!pyqe.empty()) {
        auto [cdist, cur] = pyqe.top();
        pyqe.pop();
        if (vis[cur]) continue;

        vis[cur] = true;
        for (auto [nxt, w] : adj[cur]) {
            if (dist[nxt] > dist[cur] + w) {
                dist[nxt] = dist[cur] + w;
                pyqe.push({dist[nxt], nxt});
            }
        }
    }
}

void calc(int x) {
    array<vector<int>, 2> dist = {};
    dist[0] = dist[1] = vector<int>(N, iINF);
    
    Dijkstra(s[x], dist[0]);
    Dijkstra(t[x], dist[1]);

    // debugV(dist, 0); debugV(dist, 1);

    vector<vector<int>> dag(N);
    for (int cur = 0; cur < N; cur++) {
        for (auto [nxt, w] : adj[cur]) {
            if (dist[0][cur] + w + dist[1][nxt] == dist[0][t[x]]) {
                dag[cur].push_back(nxt);
            }
        }
    }
    // for (int cur = 0; cur < N; cur++) debugV(dag, cur);

    vector<vector<int>> pth(N);
    queue<int> Q;

    Q.push(s[x]);
    pth[s[x]] = {0};
    vector<bool> vis2(N, false);

    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        if (vis2[cur]) continue;

        vis2[cur] = true;
        if ((cur != s[x ^ 1]) && (cur != t[x ^ 1])) {
            for (auto nxt : dag[cur]) {
                if (in[nxt]) {
                    for (auto p : pth[cur]) pth[nxt].push_back(p | (1 << id[nxt]));
                } else {
                    for (auto p : pth[cur]) pth[nxt].push_back(p);
                }
                Q.push(nxt);
            }
        }

        if (cur != t[x]) pth[cur].clear();
    }

    // debugV(pth, t[x]);
    for (auto p : pth[t[x]]) msk[x][p] = 1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N >> K;
    for (int u, v, w, i = 1; i <= K; i++) {
        cin >> u >> v >> w;
        u--, v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cin >> s[0] >> t[0] >> s[1] >> t[1];
    s[0]--, t[0]--, s[1]--, t[1]--;
    
    for (int i = 0; i < N; i++) in[i] = true;
    in[s[0]] = in[t[0]] = in[s[1]] = in[t[1]] = false;

    for (int t = 0, i = 0; i < N; i++) {
        if (!in[i]) continue;
        id[i] = t++;
    }

    for (int i = 0; i <= 1; i++) calc(i);

    // SOS
    int M = 1 << (N-4);
    int MX = M - 1;
    for (int i = 0; i < N-4; i++) {
        for (int m = 0; m < M; m++) {
            if (m & (1 << i)) msk[1][m] += msk[1][m ^ (1 << i)];
        }
    }

    ll ans = 0;
    for (int m = 0; m < M; m++) {
        if (msk[0][m]) ans = ans + (ll)msk[1][MX ^ m];
    }
    cout << ans << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5540kb

input:

4 4
1 2 2
2 3 1
1 3 1
3 4 1
1 2 3 4

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

4 3
1 2 1
2 3 1
3 4 1
1 3 2 4

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5504kb

input:

6 8
1 4 1
1 3 1
4 2 1
3 2 1
1 2 2
1 5 1
5 2 1
5 6 2
1 2 6 5

output:

3

result:

ok single line: '3'

Test #4:

score: -100
Wrong Answer
time: 13ms
memory: 11384kb

input:

24 276
1 2 117
1 3 36
1 4 247
1 5 150
1 6 215
1 7 232
1 8 161
1 9 209
1 10 190
1 11 4
1 12 102
1 13 281
1 14 301
1 15 32
1 16 138
1 17 114
1 18 304
1 19 141
1 20 105
1 21 64
1 22 75
1 23 23
1 24 237
2 3 153
2 4 364
2 5 267
2 6 332
2 7 349
2 8 278
2 9 326
2 10 307
2 11 113
2 12 219
2 13 398
2 14 418
...

output:

46989

result:

wrong answer 1st lines differ - expected: '3486784401', found: '46989'