#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