## #2031578

Solution for 2732: Modern Announce Network by dohatsu

Source Code Status Test Cases
Policy: public     Reviewed: 63
00.09 sec    20156 KB    88 lines     1658 bytes    2016-10-14 19:08
```#include<bits/stdc++.h>
using namespace std;
struct edge{int to,cost;};
typedef pair<int,int> P;
#define MAX_N 100005

int N,M,A[3];
vector< edge > G[MAX_N];
int D[(1<<3)][MAX_N];

void dijkstra(int bit,int* d){
for(int i=0;i<MAX_N;i++)d[i]=1e9;
priority_queue< P , vector<P> , greater<P> > Q;

if( __builtin_popcount(bit) == 1){
for(int i=0;i<3;i++){
if(bit>>i&1){
Q.push(P(0,N+i));
d[N+i]=0;
}
}
}else{
for(int i=0;i<N+3;i++){
d[i]=0;
for(int j=0;j<3;j++){
if(bit>>j&1){
d[i]+=D[(1<<j)][i];
}
}
Q.push(P(d[i],i));
}
}

while(!Q.empty()){
P p=Q.top();Q.pop();
int pos=p.second;
int cost=p.first;
if(d[pos]<cost)continue;
for(int i=0;i<(int)G[pos].size();i++){
edge e=G[pos][i];
if(cost+e.cost<d[e.to]){
d[e.to]=cost+e.cost;
Q.push(P(d[e.to],e.to));
}
}
}
}

int main(){
scanf("%d",&N);
for(int k=0;k<3;k++)scanf("%d",&A[k]);
for(int k=0;k<3;k++){
for(int i=0;i<A[k];i++){
int id;
scanf("%d",&id);
id--;
G[N+k].push_back( (edge){id,0} );
G[id].push_back( (edge){N+k,0} );
}
}
scanf("%d",&M);
for(int i=0;i<M;i++){
int a,b;
scanf("%d %d",&a,&b);
a--,b--;
G[a].push_back((edge){b,1});
G[b].push_back((edge){a,1});
}

for(int k=1;k<(1<<3);k++)dijkstra(k,D[k]);
int ans=1e9,ans2=-1;

for(int i=0;i<N;i++){
for(int j=0;j<(1<<3);j++){
int k=(1<<3)-1-j;
int cost=D[j][i]+D[k][i];
if(ans>cost){
ans=cost;
ans2=i;
}
}
}

printf("%d %d\n",ans,ans2+1);
return 0;
}

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 65/65 C++ CPU: 00.09 sec Memory: 20156 KB Length: 1658 B 2016-10-14 19:08 2016-10-14 19:08
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.00 sec 8320 KB Case #2: : Accepted 00.00 sec 8268 KB Case #3: : Accepted 00.00 sec 8188 KB Case #4: : Accepted 00.00 sec 8316 KB Case #5: : Accepted 00.00 sec 8308 KB Case #6: : Accepted 00.03 sec 11424 KB Case #7: : Accepted 00.00 sec 8556 KB Case #8: : Accepted 00.07 sec 17852 KB Case #9: : Accepted 00.03 sec 11592 KB Case #10: : Accepted 00.06 sec 19740 KB Case #11: : Accepted 00.06 sec 16480 KB Case #12: : Accepted 00.06 sec 20156 KB Case #13: : Accepted 00.07 sec 17880 KB Case #14: : Accepted 00.06 sec 14180 KB Case #15: : Accepted 00.06 sec 15288 KB Case #16: : Accepted 00.02 sec 10076 KB Case #17: : Accepted 00.07 sec 18844 KB Case #18: : Accepted 00.08 sec 19368 KB Case #19: : Accepted 00.03 sec 10920 KB Case #20: : Accepted 00.09 sec 19340 KB Case #21: : Accepted 00.05 sec 13808 KB Case #22: : Accepted 00.00 sec 8752 KB Case #23: : Accepted 00.01 sec 8736 KB Case #24: : Accepted 00.01 sec 8964 KB Case #25: : Accepted 00.01 sec 9096 KB Case #26: : Accepted 00.01 sec 8960 KB Case #27: : Accepted 00.01 sec 9004 KB Case #28: : Accepted 00.00 sec 8716 KB Case #29: : Accepted 00.01 sec 8736 KB Case #30: : Accepted 00.00 sec 8656 KB Case #31: : Accepted 00.00 sec 8348 KB Case #32: : Accepted 00.01 sec 8840 KB Case #33: : Accepted 00.00 sec 8788 KB Case #34: : Accepted 00.00 sec 8412 KB Case #35: : Accepted 00.00 sec 8384 KB Case #36: : Accepted 00.00 sec 8400 KB Case #37: : Accepted 00.00 sec 8576 KB Case #38: : Accepted 00.00 sec 8468 KB Case #39: : Accepted 00.03 sec 14112 KB Case #40: : Accepted 00.00 sec 8300 KB Case #41: : Accepted 00.01 sec 9880 KB Case #42: : Accepted 00.02 sec 12712 KB Case #43: : Accepted 00.03 sec 13228 KB Case #44: : Accepted 00.05 sec 15508 KB Case #45: : Accepted 00.00 sec 9476 KB Case #46: : Accepted 00.07 sec 16224 KB Case #47: : Accepted 00.06 sec 16204 KB Case #48: : Accepted 00.06 sec 16260 KB Case #49: : Accepted 00.06 sec 16248 KB Case #50: : Accepted 00.06 sec 16188 KB Case #51: : Accepted 00.06 sec 16204 KB Case #52: : Accepted 00.07 sec 15984 KB Case #53: : Accepted 00.06 sec 16256 KB Case #54: : Accepted 00.01 sec 8676 KB Case #55: : Accepted 00.01 sec 8812 KB Case #56: : Accepted 00.01 sec 9104 KB Case #57: : Accepted 00.01 sec 9096 KB Case #58: : Accepted 00.01 sec 8884 KB Case #59: : Accepted 00.01 sec 8996 KB Case #60: : Accepted 00.01 sec 8784 KB Case #61: : Accepted 00.01 sec 8776 KB Case #62: : Accepted 00.01 sec 8744 KB Case #63: : Accepted 00.00 sec 8864 KB Case #64: : Accepted 00.00 sec 8712 KB Case #65: : Accepted 00.00 sec 8664 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )
Comments

Under Construction.

Categories

Free Tags