QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142212 | #1972. JJ Rally | Joe_yue6 | WA | 149ms | 189804kb | C++14 | 2.9kb | 2023-08-18 17:31:18 | 2023-08-18 17:31:21 |
Judging History
answer
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
int const N = 1e3, M = 1048577, N1 = 20, M1 = 30;
int s[2], t[2], dis[M1]; //所有的点需要平移
struct stu1 {
int x, y, w;
} ed[N];
struct stu2 {
int y, nex, w;
} e[N * 2];
long long a[M1], g[2][M], lin[M1], cnt, tot, pw[M], n, m, f[M][N1]; //sosdp一下
int Get(int x, int s1, int t1) {
if (x == s1) return n;
if (x == t1) return n + 1;
int y = lower_bound(a, a + cnt, x) - a; //从0开始
if (x != a[y]) return n + 2;
return y;
}
void work(int x, int y, int w) {
e[++tot] = (stu2) {
y, lin[x], w
};
lin[x] = tot;
}
bool fl[M1];
#define fi first
#define se second
int lb(int x) {
return x & (-x);
}
void sol(int s1, int t1, int op) {
if (s1 == t1) {
g[op][0] = 1;
return;
}
tot = 0;
for (int i = 0; i <= n + 1; i++) lin[i] = 0, dis[i] = 1e9, fl[i] = 0; //一共是cnt个点
int x, y, w;
for (int i = 1; i <= m; i++) {
x = ed[i].x;
y = ed[i].y;
w = ed[i].w;
x = Get(x, s1, t1);
y = Get(y, s1, t1);
if (x == n + 2 || y == n + 2) continue;
work(x, y, w);
work(y, x, w);
}
dis[n] = 0;
priority_queue<pair<int, int>> q;
q.push(mp(0, n));
while (q.size()) {
x = q.top().se;
q.pop();
if (fl[x]) continue;
fl[x] = 1;
for (int i = lin[x]; i; i = e[i].nex) {
y = e[i].y;
if (dis[y] > dis[x] + e[i].w) {
dis[y] = dis[x] + e[i].w;
q.push(mp(-dis[y], y));
}
}
}
for (int i = lin[n]; i; i = e[i].nex) {
y = e[i].y;
if (e[i].w == dis[y]) {
if (y == n + 1) {
g[op][0]++;
//cout<<"qwq"<<endl;
} else f[1 << y][y]++;
}
}
int w1;
for (int i = 1; i < (1 << cnt); i++) {
w1 = i;
while (w1) {
int j = pw[lb(w1)];
w1 -= lb(w1);
if (f[i][j]) {
for (int k = lin[j]; k; k = e[k].nex) {
y = e[k].y;
w = e[k].w;
if (dis[j] + w == dis[y]) {
if (y == n + 1) g[op][i] += f[i][j];
else f[(1 << y) | i][y] += f[i][j];
}
}
}
}
}
memset(f, 0, sizeof(f));
}
void pd() {
if (s[0] == s[1] || t[0] == t[1] || s[0] == t[1] || s[1] == t[0]) {
printf("%d", 0);
exit(0);
}
}
int main() {
scanf("%d%d", &n, &m);
int x, y, w;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &w);
ed[i] = (stu1) {
x, y, w
};
} //s=n点 t n+1点 [0,n-1]
scanf("%d%d%d%d", &s[0], &t[0], &s[1], &t[1]);
pd();
for (int i = 1; i <= n; i++)
if (i != s[0] && i != s[1] && i != t[0] && i != t[1]) a[cnt++] = i;
for (int i = 0; i < cnt; i++) pw[1 << i] = i;
sol(s[0], t[0], 0);
sol(s[1], t[1], 1);
int sum = (1 << cnt);
for (int i = 0; i < cnt; i++) //sosdp
for (int s = 0; s < sum; s++)
if (s & (1 << i)) g[0][s] += g[0][s ^ (1 << i)];
long long ans = 0;
sum--;
// cout<<g[0][0]<<endl;
for (int s = 0; s <= sum; s++) {
ans += 1ll * g[1][s] * g[0][sum ^ s];
}
printf("%lld", ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 19ms
memory: 171544kb
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: 12ms
memory: 167928kb
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: 19ms
memory: 168968kb
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: 0
Accepted
time: 149ms
memory: 189804kb
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:
3486784401
result:
ok single line: '3486784401'
Test #5:
score: 0
Accepted
time: 119ms
memory: 187700kb
input:
24 276 1 2 48 1 3 81 1 4 233 1 5 362 1 6 37 1 7 49 1 8 17 1 9 36 1 10 327 1 11 76 1 12 271 1 13 169 1 14 124 1 15 3 1 16 421 1 17 210 1 18 144 1 19 293 1 20 18 1 21 98 1 22 392 1 23 398 1 24 226 2 3 33 2 4 281 2 5 410 2 6 85 2 7 98 2 8 65 2 9 12 2 10 376 2 11 124 2 12 319 2 13 217 2 14 173 2 15 45 2...
output:
535122674
result:
ok single line: '535122674'
Test #6:
score: 0
Accepted
time: 56ms
memory: 180336kb
input:
23 253 1 2 365 1 3 199 1 4 169 1 5 70 1 6 36 1 7 2 1 8 119 1 9 387 1 10 383 1 11 140 1 12 138 1 13 318 1 14 94 1 15 326 1 16 84 1 17 239 1 18 160 1 19 45 1 20 250 1 21 283 1 22 17 1 23 116 2 3 166 2 4 196 2 5 295 2 6 329 2 7 367 2 8 246 2 9 22 2 10 18 2 11 226 2 12 228 2 13 47 2 14 271 2 15 39 2 16 ...
output:
190681453
result:
ok single line: '190681453'
Test #7:
score: 0
Accepted
time: 135ms
memory: 189600kb
input:
24 276 1 2 278 1 3 214 1 4 18 1 5 128 1 6 87 1 7 47 1 8 325 1 9 89 1 10 189 1 11 363 1 12 88 1 13 183 1 14 215 1 15 280 1 16 146 1 17 191 1 18 315 1 19 115 1 20 55 1 21 241 1 22 267 1 23 314 1 24 17 2 3 64 2 4 260 2 5 150 2 6 191 2 7 231 2 8 47 2 9 367 2 10 89 2 11 84 2 12 366 2 13 95 2 14 63 2 15 2...
output:
1719666670
result:
ok single line: '1719666670'
Test #8:
score: 0
Accepted
time: 36ms
memory: 170828kb
input:
20 190 1 2 35 1 3 74 1 4 11 1 5 152 1 6 147 1 7 225 1 8 46 1 9 65 1 10 311 1 11 242 1 12 189 1 13 115 1 14 346 1 15 64 1 16 276 1 17 13 1 18 217 1 19 196 1 20 31 2 3 39 2 4 24 2 5 117 2 6 112 2 7 190 2 8 81 2 9 30 2 10 276 2 11 207 2 12 154 2 13 80 2 14 311 2 15 99 2 16 241 2 17 48 2 18 182 2 19 161...
output:
29733571
result:
ok single line: '29733571'
Test #9:
score: 0
Accepted
time: 21ms
memory: 170048kb
input:
19 171 1 2 87 1 3 130 1 4 199 1 5 47 1 6 253 1 7 323 1 8 103 1 9 47 1 10 212 1 11 312 1 12 76 1 13 168 1 14 274 1 15 353 1 16 12 1 17 205 1 18 169 1 19 34 2 3 42 2 4 113 2 5 134 2 6 166 2 7 236 2 8 16 2 9 40 2 10 125 2 11 226 2 12 163 2 13 81 2 14 188 2 15 267 2 16 99 2 17 117 2 18 82 2 19 53 3 4 70...
output:
3711731
result:
ok single line: '3711731'
Test #10:
score: 0
Accepted
time: 70ms
memory: 180248kb
input:
23 253 1 2 123 1 3 203 1 4 83 1 5 73 1 6 128 1 7 191 1 8 139 1 9 261 1 10 233 1 11 180 1 12 27 1 13 205 1 14 76 1 15 57 1 16 143 1 17 35 1 18 80 1 19 306 1 20 282 1 21 110 1 22 118 1 23 316 2 3 326 2 4 206 2 5 196 2 6 5 2 7 314 2 8 262 2 9 383 2 10 356 2 11 303 2 12 96 2 13 328 2 14 199 2 15 66 2 16...
output:
250401531
result:
ok single line: '250401531'
Test #11:
score: 0
Accepted
time: 20ms
memory: 169916kb
input:
4 6 1 2 47 1 3 88 1 4 21 2 3 41 2 4 26 3 4 67 3 2 4 1
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 16ms
memory: 170016kb
input:
5 10 1 2 36 1 3 52 1 4 23 1 5 20 2 3 16 2 4 13 2 5 16 3 4 29 3 5 32 4 5 3 4 5 3 1
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 21ms
memory: 170784kb
input:
6 15 1 2 36 1 3 66 1 4 90 1 5 77 1 6 47 2 3 30 2 4 54 2 5 41 2 6 11 3 4 24 3 5 11 3 6 19 4 5 13 4 6 43 5 6 30 1 3 5 6
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 24ms
memory: 171492kb
input:
7 21 1 2 37 1 3 51 1 4 41 1 5 3 1 6 2 1 7 16 2 3 14 2 4 78 2 5 34 2 6 35 2 7 21 3 4 92 3 5 48 3 6 49 3 7 35 4 5 44 4 6 43 4 7 57 5 6 1 5 7 13 6 7 14 5 2 1 7
output:
2
result:
ok single line: '2'
Test #15:
score: 0
Accepted
time: 20ms
memory: 171332kb
input:
8 28 1 2 117 1 3 23 1 4 111 1 5 34 1 6 57 1 7 106 1 8 65 2 3 94 2 4 6 2 5 151 2 6 60 2 7 11 2 8 52 3 4 88 3 5 57 3 6 34 3 7 83 3 8 42 4 5 145 4 6 54 4 7 5 4 8 46 5 6 91 5 7 140 5 8 99 6 7 49 6 8 8 7 8 41 8 2 3 7
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 20ms
memory: 170996kb
input:
9 36 1 2 145 1 3 17 1 4 32 1 5 67 1 6 81 1 7 114 1 8 18 1 9 109 2 3 162 2 4 113 2 5 78 2 6 64 2 7 31 2 8 163 2 9 36 3 4 49 3 5 84 3 6 98 3 7 131 3 8 1 3 9 126 4 5 35 4 6 49 4 7 82 4 8 50 4 9 77 5 6 14 5 7 47 5 8 85 5 9 42 6 7 33 6 8 99 6 9 28 7 8 132 7 9 5 8 9 127 7 8 5 2
output:
72
result:
ok single line: '72'
Test #17:
score: 0
Accepted
time: 12ms
memory: 170760kb
input:
10 45 1 2 37 1 3 96 1 4 134 1 5 75 1 6 57 1 7 121 1 8 79 1 9 39 1 10 66 2 3 133 2 4 171 2 5 38 2 6 94 2 7 158 2 8 116 2 9 76 2 10 103 3 4 38 3 5 171 3 6 39 3 7 25 3 8 17 3 9 57 3 10 30 4 5 209 4 6 77 4 7 13 4 8 55 4 9 95 4 10 68 5 6 132 5 7 196 5 8 154 5 9 114 5 10 141 6 7 64 6 8 22 6 9 18 6 10 9 7 ...
output:
36
result:
ok single line: '36'
Test #18:
score: 0
Accepted
time: 16ms
memory: 170760kb
input:
11 55 1 2 24 1 3 32 1 4 75 1 5 53 1 6 13 1 7 49 1 8 134 1 9 158 1 10 74 1 11 100 2 3 8 2 4 51 2 5 29 2 6 11 2 7 25 2 8 110 2 9 134 2 10 50 2 11 76 3 4 43 3 5 21 3 6 19 3 7 17 3 8 102 3 9 126 3 10 42 3 11 68 4 5 22 4 6 62 4 7 26 4 8 59 4 9 83 4 10 1 4 11 25 5 6 40 5 7 4 5 8 81 5 9 105 5 10 21 5 11 47...
output:
2
result:
ok single line: '2'
Test #19:
score: 0
Accepted
time: 20ms
memory: 171536kb
input:
12 66 1 2 14 1 3 72 1 4 27 1 5 42 1 6 35 1 7 41 1 8 148 1 9 20 1 10 95 1 11 144 1 12 126 2 3 58 2 4 13 2 5 56 2 6 49 2 7 27 2 8 134 2 9 34 2 10 81 2 11 130 2 12 112 3 4 45 3 5 114 3 6 107 3 7 31 3 8 76 3 9 92 3 10 23 3 11 72 3 12 54 4 5 69 4 6 62 4 7 14 4 8 121 4 9 47 4 10 68 4 11 117 4 12 99 5 6 7 ...
output:
32
result:
ok single line: '32'
Test #20:
score: 0
Accepted
time: 11ms
memory: 169940kb
input:
13 78 1 2 131 1 3 89 1 4 199 1 5 118 1 6 31 1 7 148 1 8 34 1 9 14 1 10 162 1 11 60 1 12 61 1 13 48 2 3 42 2 4 68 2 5 13 2 6 162 2 7 17 2 8 97 2 9 117 2 10 31 2 11 191 2 12 192 2 13 83 3 4 110 3 5 29 3 6 120 3 7 59 3 8 55 3 9 75 3 10 73 3 11 149 3 12 150 3 13 41 4 5 81 4 6 230 4 7 51 4 8 165 4 9 185 ...
output:
96
result:
ok single line: '96'
Test #21:
score: 0
Accepted
time: 15ms
memory: 170752kb
input:
14 91 1 2 60 1 3 38 1 4 76 1 5 6 1 6 36 1 7 65 1 8 208 1 9 55 1 10 183 1 11 149 1 12 135 1 13 94 1 14 91 2 3 98 2 4 136 2 5 54 2 6 24 2 7 5 2 8 268 2 9 115 2 10 243 2 11 209 2 12 195 2 13 154 2 14 31 3 4 38 3 5 44 3 6 74 3 7 103 3 8 170 3 9 17 3 10 145 3 11 111 3 12 97 3 13 56 3 14 129 4 5 82 4 6 11...
output:
432
result:
ok single line: '432'
Test #22:
score: 0
Accepted
time: 32ms
memory: 174344kb
input:
22 231 1 2 98 1 3 104 1 4 59 1 5 12 1 6 300 1 7 215 1 8 284 1 9 197 1 10 219 1 11 183 1 12 50 1 13 70 1 14 114 1 15 35 1 16 69 1 17 244 1 18 211 1 19 36 1 20 101 1 21 90 1 22 148 2 3 202 2 4 157 2 5 86 2 6 398 2 7 313 2 8 382 2 9 295 2 10 317 2 11 281 2 12 148 2 13 28 2 14 212 2 15 63 2 16 167 2 17 ...
output:
36
result:
ok single line: '36'
Test #23:
score: 0
Accepted
time: 44ms
memory: 180740kb
input:
23 253 1 2 285 1 3 105 1 4 161 1 5 32 1 6 243 1 7 296 1 8 286 1 9 207 1 10 125 1 11 20 1 12 205 1 13 263 1 14 81 1 15 245 1 16 146 1 17 26 1 18 173 1 19 195 1 20 109 1 21 69 1 22 64 1 23 100 2 3 180 2 4 446 2 5 317 2 6 42 2 7 11 2 8 1 2 9 492 2 10 410 2 11 305 2 12 80 2 13 22 2 14 204 2 15 530 2 16 ...
output:
248832
result:
ok single line: '248832'
Test #24:
score: 0
Accepted
time: 77ms
memory: 189548kb
input:
24 276 1 2 144 1 3 208 1 4 277 1 5 375 1 6 446 1 7 118 1 8 91 1 9 177 1 10 335 1 11 166 1 12 237 1 13 368 1 14 40 1 15 182 1 16 306 1 17 38 1 18 87 1 19 409 1 20 58 1 21 48 1 22 312 1 23 59 1 24 346 2 3 64 2 4 133 2 5 231 2 6 302 2 7 26 2 8 235 2 9 33 2 10 191 2 11 22 2 12 93 2 13 224 2 14 104 2 15 ...
output:
663552
result:
ok single line: '663552'
Test #25:
score: 0
Accepted
time: 38ms
memory: 176656kb
input:
23 253 1 2 250 1 3 128 1 4 54 1 5 274 1 6 216 1 7 201 1 8 115 1 9 78 1 10 58 1 11 183 1 12 149 1 13 294 1 14 63 1 15 270 1 16 211 1 17 43 1 18 142 1 19 103 1 20 35 1 21 202 1 22 1 1 23 11 2 3 376 2 4 196 2 5 26 2 6 33 2 7 49 2 8 136 2 9 171 2 10 307 2 11 67 2 12 101 2 13 46 2 14 312 2 15 20 2 16 39 ...
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 48ms
memory: 179568kb
input:
23 253 1 2 104 1 3 92 1 4 5 1 5 52 1 6 181 1 7 30 1 8 29 1 9 44 1 10 70 1 11 150 1 12 201 1 13 9 1 14 29 1 15 136 1 16 135 1 17 231 1 18 149 1 19 105 1 20 55 1 21 31 1 22 171 1 23 11 2 3 12 2 4 99 2 5 155 2 6 76 2 7 74 2 8 76 2 9 61 2 10 174 2 11 46 2 12 97 2 13 113 2 14 133 2 15 31 2 16 239 2 17 12...
output:
4080
result:
ok single line: '4080'
Test #27:
score: 0
Accepted
time: 33ms
memory: 176468kb
input:
23 253 1 2 3 1 3 2 1 4 2 1 5 2 1 6 3 1 7 3 1 8 1 1 9 1 1 10 1 1 11 2 1 12 3 1 13 3 1 14 2 1 15 1 1 16 1 1 17 3 1 18 3 1 19 2 1 20 2 1 21 3 1 22 2 1 23 3 2 3 3 2 4 1 2 5 2 2 6 2 2 7 2 2 8 1 2 9 1 2 10 3 2 11 1 2 12 3 2 13 2 2 14 2 2 15 3 2 16 1 2 17 3 2 18 2 2 19 1 2 20 3 2 21 3 2 22 1 2 23 2 3 4 1 3...
output:
4
result:
ok single line: '4'
Test #28:
score: -100
Wrong Answer
time: 19ms
memory: 170712kb
input:
6 15 1 2 1 1 3 3 1 4 2 1 5 1 1 6 1 2 3 2 2 4 1 2 5 2 2 6 1 3 4 3 3 5 3 3 6 1 4 5 3 4 6 1 5 6 2 4 3 2 6
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'