QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212581 | #1972. JJ Rally | Zanite# | WA | 56ms | 20772kb | C++17 | 3.6kb | 2023-10-13 17:32:54 | 2023-10-13 17:32:54 |
Judging History
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};
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
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)];
}
}
int ans = 0;
for (int m = 0; m < M; m++) {
if (msk[0][m]) ans = (ans + msk[1][MX ^ m]);
}
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5680kb
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: 0ms
memory: 3576kb
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: 5928kb
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: 56ms
memory: 20772kb
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:
-808182895
result:
wrong answer 1st lines differ - expected: '3486784401', found: '-808182895'