#783171 (C++14) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: monnu
• 提出日時: 2022-07-30 16:50:16
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 847 ms / 1,000 ms
• コード長: 6,508 bytes
• コンパイル時間: 3,702 ms
• 実行使用メモリ: 6,956 KB
• スコア: 8,606,493
• 最終ジャッジ日時: 2022-07-30 16:51:00
• 合計ジャッジ時間: 30,865 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	817 ms; 4,900 KB
testcase_01	AC	830 ms; 4,908 KB
testcase_02	AC	817 ms; 4,900 KB
testcase_03	AC	844 ms; 4,904 KB
testcase_04	AC	816 ms; 4,904 KB
testcase_05	AC	817 ms; 4,904 KB
testcase_06	AC	817 ms; 4,904 KB
testcase_07	AC	815 ms; 4,904 KB
testcase_08	AC	817 ms; 4,900 KB
testcase_09	AC	817 ms; 6,956 KB
testcase_10	AC	818 ms; 4,904 KB
testcase_11	AC	844 ms; 6,948 KB
testcase_12	AC	820 ms; 4,904 KB
testcase_13	AC	847 ms; 4,904 KB
testcase_14	AC	817 ms; 4,900 KB
testcase_15	AC	817 ms; 4,904 KB
testcase_16	AC	816 ms; 6,952 KB
testcase_17	AC	816 ms; 6,952 KB
testcase_18	AC	816 ms; 4,904 KB
testcase_19	AC	817 ms; 6,948 KB
testcase_20	AC	817 ms; 4,904 KB
testcase_21	AC	817 ms; 4,900 KB
testcase_22	AC	817 ms; 4,904 KB
testcase_23	AC	818 ms; 4,904 KB
testcase_24	AC	818 ms; 4,904 KB
testcase_25	AC	818 ms; 6,948 KB
testcase_26	AC	817 ms; 6,952 KB
testcase_27	AC	817 ms; 6,952 KB
testcase_28	AC	819 ms; 4,904 KB
testcase_29	AC	819 ms; 4,900 KB

コンパイルメッセージ

main.cpp: 関数 ‘int main()’ 内:
main.cpp:232:29: 警告: ‘currentBase’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  232 |     currentBase=(currentBase+1)%M;
      |                 ~~~~~~~~~~~~^~~

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll=long long;
using Graph=vector<vector<int>>;
#define INF 1000000000
#define MOD 998244353
#define MAX 500

int N,M;
int alpha = 5;

random_device seed;
mt19937 engine(seed());
uniform_real_distribution<> uniform_real_dist(0.0,1.0);
clock_t start_t,end_t;
double elapsed_time;
//実行制限時間-ε
double time_limit=0.2;
//初期温度
double T0=1e6;
//最終温度
double T1=1e2;

void two_opt(vector<int> &path, vector<vector<int>> &dist, int &S)
{
  start_t=clock();
  int n=path.size();
  end_t=clock();
  elapsed_time=(double)(end_t-start_t)/CLOCKS_PER_SEC;
  // path[1, n-2]の順番を変更
  while (elapsed_time <= time_limit) {
    double T=pow(T0,1.0-elapsed_time/time_limit)*pow(T1,elapsed_time/time_limit);
    int left  = rand()%(n-2) + 1;
    int right = rand()%(n-2) + 1;
    if (left == right) {
      continue;
    }
    if (right < left) {
      swap(left, right);
    }
    int deltaS = 0.0;
    deltaS -= dist[path[left-1]][path[left]] + dist[path[right]][path[right+1]];
    deltaS += dist[path[left-1]][path[right]] + dist[path[left]][path[right+1]];
    int diff = round(1.0e9/(1.0e3 + sqrt(S+deltaS))) - round(1.0e9/(1.0e3 + sqrt(S)));
    //遷移確率
    double p=min<double>(1.0,exp(diff/T));
    if(uniform_real_dist(engine)<=p){
      S += deltaS;
      reverse(path.begin() + left, path.begin() + (right+1));
    }
    end_t=clock();
    elapsed_time=(double)(end_t-start_t)/CLOCKS_PER_SEC;
  }
}

void update_base_place(vector<int> &ans,vector<int> &a,vector<int> &b,vector<int> &x,vector<int> &y,vector<vector<int>> &dist,vector<vector<int>> &nextNode)
{
  // 基地の位置を変更
  vector<int> pathCnt(M,0);
  for(int i=0;i<M;i++){
    x[i] = 0;
    y[i] = 0;
  }
  for(int i=0;i<(int)ans.size()-1;i++){
    if(ans[i]<N&&ans[i+1]>=N){
      int v=ans[i+1]-N;
      int u=ans[i];
      pathCnt[v]++;
      x[v]+=a[u];
      y[v]+=b[u];
    }
    else if(ans[i]>=N&&ans[i+1]<N){
      int v=ans[i]-N;
      int u=ans[i+1];
      pathCnt[v]++;
      x[v]+=a[u];
      y[v]+=b[u];
    }
  }
  for(int i=0;i<M;i++){
    if(pathCnt[i]>0){
      x[i]/=pathCnt[i];
      y[i]/=pathCnt[i];
    }
    else{
      x[i]=rand()%1000;
      y[i]=rand()%1000;
    }
  }

  // distテーブルの更新
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      dist[i][j] = alpha*alpha * ((a[i]-a[j])*(a[i]-a[j]) + (b[i]-b[j])*(b[i]-b[j]));
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      dist[i][N+j] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
      dist[N+j][i] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
    }
  }
  for(int i=0;i<M;i++){
    for(int j=0;j<M;j++){
      dist[N+i][N+j] = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
    }
  }
  for(int i=0;i<N+M;i++){
    for(int j=0;j<N+M;j++){
      nextNode[i][j]=j;
    }
  }

  for(int k=0;k<N+M;k++){
    for(int i=0;i<N+M;i++){
      for(int j=0;j<N+M;j++){
        if(dist[i][k]+dist[k][j]<dist[i][j]){
          dist[i][j]=dist[i][k]+dist[k][j];
          nextNode[i][j]=nextNode[i][k];
        }
      }
    }
  }
}

int main(){
  cin>>N>>M;
  vector<int> a(N), b(N);
  for(int i=0;i<N;i++){
    cin>>a[i]>>b[i];
  }

  /*
  vector<pair<int,int>> planetCnt(N);
  for(int i=0;i<N;i++){
    planetCnt[i].second=i;
    planetCnt[i].first=0;
  }
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])<=100*100){
        planetCnt[i].first++;
        planetCnt[j].first++;
      }
    }
  }
  sort(planetCnt.begin(),planetCnt.end());

  vector<int> x(M),y(M);
  int k=0;
  for(int i=N-1;i>=0;i--){
    bool flag=true;
    for(int j=0;j<k;j++){
      if((a[i]-x[j])*(a[i]-x[j])+(b[i]-y[j])*(b[i]-y[j])<=100*100){
        flag=false;
        break;
      }
    }
    if(flag){
      x[k]=a[i];
      y[k]=b[i];
      k++;
      if(k==M){
        break;
      }
    }
  }
  */

  int delta = 400;
  vector<int> x={500+delta, 500+delta, 500, 500-delta, 500-delta, 500-delta, 500, 500+delta};
  vector<int> y={500, 500+delta, 500+delta, 500+delta, 500, 500-delta, 500-delta, 500-delta};
  vector<vector<int>> dist(N+M,vector<int>(N+M,INF));
  vector<vector<int>> nextNode(N+M,vector<int>(N+M));
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      dist[i][j] = alpha*alpha * ((a[i]-a[j])*(a[i]-a[j]) + (b[i]-b[j])*(b[i]-b[j]));
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      dist[i][N+j] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
      dist[N+j][i] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
    }
  }
  for(int i=0;i<M;i++){
    for(int j=0;j<M;j++){
      dist[N+i][N+j] = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
    }
  }
  for(int i=0;i<N+M;i++){
    for(int j=0;j<N+M;j++){
      nextNode[i][j]=j;
    }
  }

  for(int k=0;k<N+M;k++){
    for(int i=0;i<N+M;i++){
      for(int j=0;j<N+M;j++){
        if(dist[i][k]+dist[k][j]<dist[i][j]){
          dist[i][j]=dist[i][k]+dist[k][j];
          nextNode[i][j]=nextNode[i][k];
        }
      }
    }
  }

  vector<vector<int>> nearbyPlanets(M);
  int currentBase;
  for(int i=0;i<N;i++){
    int k=0;
    for(int j=1;j<M;j++){
      if(dist[i][j]<dist[i][k]){
        k=j;
      }
    }
    nearbyPlanets[k].push_back(i);
    if(i==0){
      currentBase=k;
    }
  }
  vector<int> path;
  path.push_back(0);
  for(int i=0;i<M;i++){
    for(int p:nearbyPlanets[currentBase]){
      if(p!=0){
        path.push_back(p);
      }
    }
    currentBase=(currentBase+1)%M;
  }
  path.push_back(0);
  //assert(path.size()==N+1);

  int loopCnt=4;
  for(int ii=0;ii<loopCnt;ii++){
    int S=0;
    for(int i=0;i<N;i++){
      S+=dist[path[i]][path[i+1]];
    }

    two_opt(path, dist, S);

    // 経路を出す
    vector<int> ans;
    ans.push_back(path[0]);
    for(int i=0;i<N;i++){
      int v=path[i];
      while(v!=path[i+1]){
        v=nextNode[v][path[i+1]];
        ans.push_back(v);
      }
    }
    // 基地の位置を変更
    update_base_place(ans,a,b,x,y,dist,nextNode);

    if(ii==loopCnt-1){
      // 出力
      for(int i=0;i<M;i++){
        cout<<x[i]<<' '<<y[i]<<'\n';
      }
      cout<<ans.size()<<'\n';
      for(int i=0;i<ans.size();i++){
        if(ans[i]<N){
          cout<<"1 "<<ans[i]+1<<'\n';
        }else{
          cout<<"2 "<<(ans[i]-N)+1<<'\n';
        }
      }
    }
  }

  //int score = round(1.0e9/(1.0e3 + sqrt(S)));
  //cout<<score<<'\n';
}