QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142210 | #1972. JJ Rally | flame | WA | 157ms | 189908kb | C++14 | 2.5kb | 2023-08-18 17:24:22 | 2023-08-18 17:24:24 |
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: 22ms
memory: 170508kb
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: 22ms
memory: 168292kb
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: 23ms
memory: 170032kb
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: 157ms
memory: 189160kb
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: 125ms
memory: 188448kb
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: 54ms
memory: 182144kb
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: 131ms
memory: 189908kb
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: 20ms
memory: 171172kb
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: 170572kb
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: 80ms
memory: 182344kb
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: 13ms
memory: 170616kb
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: 12ms
memory: 169692kb
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: 18ms
memory: 170940kb
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: 27ms
memory: 170136kb
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: 12ms
memory: 171412kb
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: 19ms
memory: 171332kb
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: 24ms
memory: 171432kb
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: 21ms
memory: 171572kb
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: 15ms
memory: 170668kb
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: 23ms
memory: 170864kb
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: 20ms
memory: 170692kb
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: 28ms
memory: 176172kb
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: 59ms
memory: 180808kb
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: 66ms
memory: 187384kb
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: 32ms
memory: 177784kb
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: 42ms
memory: 178620kb
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: 48ms
memory: 176800kb
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: 16ms
memory: 170508kb
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'