QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212727 | #1972. JJ Rally | ucup-team1004 | WA | 87ms | 19720kb | C++14 | 1.6kb | 2023-10-13 20:04:34 | 2023-10-13 20:04:34 |
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=24,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){
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=0;i<n;i++)d[i][i]=0;
for(int u,v,w;m--;){
cin>>u>>v>>w,u--,v--;
a[u][v]=a[v][u]=w;
d[u][v]=d[v][u]=w;
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;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=0,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: 5476kb
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: 3440kb
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: 5408kb
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: 87ms
memory: 19720kb
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:
1162261467
result:
wrong answer 1st lines differ - expected: '3486784401', found: '1162261467'