QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212755 | #1972. JJ Rally | ucup-team1004 | WA | 101ms | 20128kb | C++14 | 1.6kb | 2023-10-13 20:21:58 | 2023-10-13 20:21:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=30,M=1<<20;
int n,m,a[N][N],d[N][N];
int s1,t1,s2,t2,vis[N],id[N];
ll g[M],h[M];
void dfs(ll *f,int u,int t,int S=0){
// debug(u,t);
for(int v=1;v<=n;v++){
if(!a[u][v]||a[u][v]+d[v][t]>d[u][t])continue;
if(v==t){
f[S]++;
}else if(!vis[v]){
dfs(f,v,t,S|(1<<id[v]));
}
}
}
int main(){
cin>>n>>m;
memset(d,0x3f,sizeof d);
for(int i=1;i<=n;i++)d[i][i]=0;
for(int u,v,w;m--;){
cin>>u>>v>>w;
a[u][v]=a[v][u]=w;
d[u][v]=d[v][u]=w;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
cin>>s1>>t1>>s2>>t2;
vis[s1]=vis[t1]=vis[s2]=vis[t2]=1;
for(int i=1,k=0;i<=n;i++){
if(!vis[i])id[i]=k++;
else id[i]=-1;
}
dfs(g,s1,t1),dfs(h,s2,t2);
int U=(1<<n-4)-1;
for(int len=1;len<U;len<<=1){
for(int i=0;i<=U;i+=len<<1){
for(int j=0;j<len;j++){
g[i|j]+=g[i|j|len],h[i|j]+=h[i|j|len];
}
}
}
for(int S=0;S<=U;S++)g[S]*=h[S];
for(int len=1;len<U;len<<=1){
for(int i=0;i<=U;i+=len<<1){
for(int j=0;j<len;j++){
g[i|j]-=g[i|j|len];
}
}
}
cout<<g[0]<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5636kb
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: 3672kb
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: 5736kb
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: 101ms
memory: 20128kb
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: 88ms
memory: 20096kb
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: 37ms
memory: 15060kb
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: 89ms
memory: 20092kb
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: 4ms
memory: 6152kb
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: 2ms
memory: 5964kb
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: 45ms
memory: 15236kb
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: 1ms
memory: 5780kb
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: -100
Wrong Answer
time: 1ms
memory: 5792kb
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:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'