結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 monnu
|
| 提出日時 | 2022-07-30 17:15:53 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 859 ms / 1,000 ms |
| コード長 | 6,897 bytes |
| コンパイル時間 | 3,887 ms |
| 実行使用メモリ | 5,160 KB |
| スコア | 8,527,723 |
| 最終ジャッジ日時 | 2022-07-30 17:17:07 |
| 合計ジャッジ時間 | 31,070 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:252:29: 警告: ‘currentBase’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
252 | 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 500int 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+M;i++){for(int j=0;j<N+M;j++){dist[i][j]=INF;}}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<int> solve_ans(vector<int> &path,vector<vector<int>> &nextNode){vector<int> ans;ans.push_back(path[0]);for(int i=0;i<(int)path.size()-1;i++){int v=path[i];while(v!=path[i+1]){v=nextNode[v][path[i+1]];ans.push_back(v);}}return ans;}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 = 200;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 = solve_ans(path,nextNode);// 基地の位置を変更update_base_place(ans,a,b,x,y,dist,nextNode);//経路再計算ans=solve_ans(path,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 S=0;for(int i=0;i<N;i++){S+=dist[path[i]][path[i+1]];}int score = round(1.0e9/(1.0e3 + sqrt(S)));cout<<score<<'\n';*/}}}