結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 Shun_PI
|
| 提出日時 | 2026-02-26 00:04:50 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 972 ms / 1,000 ms |
| コード長 | 12,581 bytes |
| 記録 | |
| コンパイル時間 | 3,758 ms |
| コンパイル使用メモリ | 354,944 KB |
| 実行使用メモリ | 7,968 KB |
| スコア | 52,411,764 |
| 最終ジャッジ日時 | 2026-02-26 00:06:37 |
| 合計ジャッジ時間 | 106,142 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int T_START = 360;
const int T_END = 1260;
const int T_STEP = 5;
const int NUM_TARGETS = 21;
const int NEG_INF = -999999;
const int MAX_FL = 500;
int N, R, M, K;
double px[50], py[50];
int pw[50];
struct Flight { int a, b, s, t; };
Flight sq_arr[401];
double dist_tab[50][50];
int ftime_tab[50][50];
int vsrc[50][50], vsrc_cnt[50];
int target_t[NUM_TARGETS];
int sq_lat[50][NUM_TARGETS][50];
int cached_plane_id = -1;
int base_lat_cache[50][NUM_TARGETS][50];
int plane_start[26];
int rd[26][200];
int rl[26];
mt19937 rng;
long long cum_w[50], total_w;
int sample_city() {
long long r = rng() % total_w;
int lo = 1, hi = N;
while (lo < hi) { int m=(lo+hi)/2; if(cum_w[m]<=r)lo=m+1; else hi=m; }
return lo;
}
int sample_buf(const int* buf, int n) {
if (n==1) return buf[0];
long long s=0;
for (int i=0;i<n;i++) s+=pw[buf[i]];
long long r=rng()%s, acc=0;
for (int i=0;i<n;i++){acc+=pw[buf[i]]; if(acc>r) return buf[i];}
return buf[n-1];
}
int parse_time(const char* s){int h,m;sscanf(s,"%d:%d",&h,&m);return h*60+m;}
void precompute() {
for (int i=1;i<=N;i++) for(int j=1;j<=N;j++){
double dx=px[i]-px[j],dy=py[i]-py[j];
dist_tab[i][j]=sqrt(dx*dx+dy*dy);
}
for (int i=1;i<=N;i++) for(int j=1;j<=N;j++){
if(i==j){ftime_tab[i][j]=0;continue;}
double raw=60.0*dist_tab[i][j]/800.0+40.0;
ftime_tab[i][j]=(int)ceil(raw/5.0)*5;
}
for (int j=1;j<=N;j++){
vsrc_cnt[j]=0;
for (int i=1;i<=N;i++)
if(i!=j && dist_tab[i][j]>=0.25*R)
vsrc[j][vsrc_cnt[j]++]=i;
}
for (int k=0;k<NUM_TARGETS;k++) target_t[k]=660+30*k;
cum_w[0]=0;
for (int i=1;i<=N;i++) cum_w[i]=cum_w[i-1]+pw[i];
total_w=cum_w[N];
}
Flight sq_sorted[401]; int sq_scnt;
void precompute_sq() {
sq_scnt=M; memcpy(sq_sorted,sq_arr,sizeof(Flight)*M);
sort(sq_sorted,sq_sorted+sq_scnt,[](const Flight&a,const Flight&b){return a.t>b.t;});
int lat[50];
for (int j=1;j<=N;j++) for(int k=0;k<NUM_TARGETS;k++){
for(int c=1;c<=N;c++) lat[c]=NEG_INF;
lat[j]=target_t[k];
for(int fi=0;fi<sq_scnt;fi++){
const auto&f=sq_sorted[fi];
if(lat[f.b]!=NEG_INF && f.t<=lat[f.b] && f.s>lat[f.a]) lat[f.a]=f.s;
}
memcpy(sq_lat[j][k],lat,sizeof(int)*(N+1));
}
}
Flight pfl[26][50]; int pfl_cnt[26];
void compute_base_lat(int exclude_p) {
static Flight buf[1000];
int cnt=0;
for(int q=1;q<=K;q++){
if(q==exclude_p) continue;
for(int i=0;i<pfl_cnt[q];i++) buf[cnt++]=pfl[q][i];
}
sort(buf,buf+cnt,[](const Flight&a,const Flight&b){return a.t>b.t;});
int lat[50];
for(int j=1;j<=N;j++) for(int k=0;k<NUM_TARGETS;k++){
for(int c=1;c<=N;c++) lat[c]=NEG_INF;
lat[j]=target_t[k];
for(int fi=0;fi<cnt;fi++){
const auto&f=buf[fi];
if(lat[f.b]!=NEG_INF && f.t<=lat[f.b] && f.s>lat[f.a]) lat[f.a]=f.s;
}
memcpy(base_lat_cache[j][k],lat,sizeof(int)*(N+1));
}
cached_plane_id=exclude_p;
}
long long eval_score_diff(int p) {
int p_cnt=pfl_cnt[p];
long long v=0;
int lat[50];
for(int j=1;j<=N;j++){
int wj=pw[j], vc=vsrc_cnt[j];
if(!vc) continue;
for(int k=0;k<NUM_TARGETS;k++){
memcpy(lat,base_lat_cache[j][k],sizeof(int)*(N+1));
for(int fi=p_cnt-1;fi>=0;fi--){
const auto&f=pfl[p][fi];
if(lat[f.b]!=NEG_INF && f.t<=lat[f.b] && f.s>lat[f.a]) lat[f.a]=f.s;
}
const int*sq=sq_lat[j][k], *vs=vsrc[j];
for(int vi=0;vi<vc;vi++){
int i=vs[vi];
if(sq[i]<lat[i]) v+=(long long)pw[i]*wj;
}
}
}
return v;
}
// rd[p][i]==0 means "wait 5 min at current city"
// rd[p][i]>=1 means city id
void gen_plane(int p) {
pfl_cnt[p]=0;
if(rl[p]<1) return;
int cur=plane_start[p];
int last_city=-1; // last real city
for(int i=0;i<rl[p];i++){
if(rd[p][i]==0){
// wait 5 minutes
cur+=T_STEP;
if(cur>T_END) break;
} else {
if(last_city==-1){
last_city=rd[p][i]; // starting city
} else {
int a=last_city, b=rd[p][i];
int arr=cur+ftime_tab[a][b];
if(arr>T_END) break;
pfl[p][pfl_cnt[p]++]={a,b,cur,arr};
cur=arr;
last_city=b;
}
}
}
}
Flight ci_buf[MAX_FL]; int ci_cnt;
void rebuild_ci() {
ci_cnt=0;
for(int p=1;p<=K;p++)
for(int i=0;i<pfl_cnt[p];i++)
ci_buf[ci_cnt++]=pfl[p][i];
sort(ci_buf,ci_buf+ci_cnt,[](const Flight&a,const Flight&b){return a.t>b.t;});
}
long long eval_score() {
long long v=0; int lat[50];
for(int j=1;j<=N;j++){
int wj=pw[j], vc=vsrc_cnt[j];
if(!vc) continue;
for(int k=0;k<NUM_TARGETS;k++){
for(int c=1;c<=N;c++) lat[c]=NEG_INF;
lat[j]=target_t[k];
for(int fi=0;fi<ci_cnt;fi++){
int fb=ci_buf[fi].b;
if(lat[fb]!=NEG_INF && ci_buf[fi].t<=lat[fb]){
int fa=ci_buf[fi].a;
if(ci_buf[fi].s>lat[fa]) lat[fa]=ci_buf[fi].s;
}
}
const int*sq=sq_lat[j][k], *vs=vsrc[j];
for(int vi=0;vi<vc;vi++){
int i=vs[vi];
if(sq[i]<lat[i]) v+=(long long)pw[i]*wj;
}
}
}
return v;
}
void fill_route(int p) {
// Replay existing route to find cur time and last city
int cur=plane_start[p];
int last_city=-1;
for(int i=0;i<rl[p];i++){
if(rd[p][i]==0){
cur+=T_STEP;
if(cur>T_END){rl[p]=i;return;}
} else {
if(last_city>=1){
int ft=ftime_tab[last_city][rd[p][i]];
if(cur+ft>T_END){rl[p]=i;return;}
cur+=ft;
}
last_city=rd[p][i];
}
}
if(last_city<1) return;
// Greedily extend
int cands[50],ccnt;
while(true){
ccnt=0;
for(int c=1;c<=N;c++){
if(c==last_city) continue;
if(cur+ftime_tab[last_city][c]<=T_END) cands[ccnt++]=c;
}
if(!ccnt) break;
int nx=sample_buf(cands,ccnt);
rd[p][rl[p]++]=nx;
cur+=ftime_tab[last_city][nx];
last_city=nx;
}
}
int main(){
rng.seed(chrono::steady_clock::now().time_since_epoch().count());
scanf("%d%d",&N,&R);
for(int i=1;i<=N;i++) scanf("%lf%lf%d",&px[i],&py[i],&pw[i]);
scanf("%d",&M);
for(int i=0;i<M;i++){
char ss[10],tt[10];
scanf("%d%s%d%s",&sq_arr[i].a,ss,&sq_arr[i].b,tt);
sq_arr[i].s=parse_time(ss); sq_arr[i].t=parse_time(tt);
}
scanf("%d",&K);
auto t0=chrono::steady_clock::now();
precompute(); precompute_sq();
// ---- Initial solution: staggered start times ----
long long init_best=-1;
int init_rd[26][200], init_rl[26], init_ps[26];
for(int trial=0; trial<8; trial++){
for(int p=1;p<=K;p++){
plane_start[p] = T_START;
rd[p][0]=sample_city(); rl[p]=1;
fill_route(p);
gen_plane(p);
}
rebuild_ci();
long long sc=eval_score();
if(sc>init_best){
init_best=sc;
for(int p=1;p<=K;p++){
memcpy(init_rd[p],rd[p],sizeof(int)*rl[p]);
init_rl[p]=rl[p]; init_ps[p]=plane_start[p];
}
}
}
for(int p=1;p<=K;p++){
memcpy(rd[p],init_rd[p],sizeof(int)*init_rl[p]);
rl[p]=init_rl[p]; plane_start[p]=init_ps[p];
gen_plane(p);
}
rebuild_ci();
// ---- SA (differential evaluation) ----
long long cur_score=init_best, best_score=init_best;
int best_rd[26][200], best_rl[26], best_ps[26];
for(int p=1;p<=K;p++){
memcpy(best_rd[p],rd[p],sizeof(int)*rl[p]);
best_rl[p]=rl[p]; best_ps[p]=plane_start[p];
}
const double time_limit=0.95;
int iter=0;
double cur_temp=1e13;
bool sa_timeout=false;
int old_rd_buf[200];
Flight old_pfl_buf[50];
int old_rl_v, old_ps_v, old_pfl_cnt_v;
while(!sa_timeout){
int p=rng()%K+1;
if(p!=cached_plane_id){
compute_base_lat(p);
cur_score=eval_score_diff(p);
}
for(int batch=0; batch<30 && !sa_timeout; batch++){
if((iter&127)==0){
double el=chrono::duration<double>(chrono::steady_clock::now()-t0).count();
if(el>=time_limit){sa_timeout=true;break;}
double prog=el/time_limit;
cur_temp=1e13*pow(1e-4,prog);
}
iter++;
// Save
old_rl_v=rl[p]; old_ps_v=plane_start[p]; old_pfl_cnt_v=pfl_cnt[p];
memcpy(old_rd_buf,rd[p],sizeof(int)*old_rl_v);
memcpy(old_pfl_buf,pfl[p],sizeof(Flight)*old_pfl_cnt_v);
// Mutations
int rlen=rl[p];
int mut=rng()%20;
if(mut<7 && rlen>=1){
int pos=rng()%rlen;
rd[p][pos]=sample_city();
} else if(mut<9 && rlen<190){
int pos=rng()%(rlen+1);
for(int i=rlen;i>pos;i--) rd[p][i]=rd[p][i-1];
rd[p][pos]=sample_city(); rl[p]++;
} else if(mut<11 && rlen>=2){
int pos=1+rng()%(rlen-1);
for(int i=pos;i+1<rlen;i++) rd[p][i]=rd[p][i+1];
rl[p]--;
} else if(mut<13 && rlen>=3){
int a=rng()%rlen, b=rng()%rlen;
swap(rd[p][a],rd[p][b]);
} else if(mut<15 && rlen<190 && rlen>=2){
int pos=1+rng()%(rlen-1);
for(int i=rlen;i>pos;i--) rd[p][i]=rd[p][i-1];
rd[p][pos]=0; rl[p]++;
} else if(mut<16){
for(int i=rlen-1;i>=1;i--){
if(rd[p][i]==0){
for(int j=i;j+1<rlen;j++) rd[p][j]=rd[p][j+1];
rl[p]--; break;
}
}
} else if(mut<18){
int delta=((int)(rng()%25)-12)*T_STEP;
plane_start[p]=max(T_START,min(T_END-60,plane_start[p]+delta));
} else {
rd[p][0]=sample_city(); rl[p]=1;
fill_route(p);
}
// Validate
bool ok=(rl[p]>=1 && rd[p][0]>=1 && rd[p][0]<=N);
if(ok){
int prev_city=-1;
for(int i=0;i<rl[p]&&ok;i++){
int v=rd[p][i];
if(v<0||v>N) ok=false;
else if(v>0){
if(v==prev_city) ok=false;
prev_city=v;
}
}
}
if(!ok){
memcpy(rd[p],old_rd_buf,sizeof(int)*old_rl_v);
rl[p]=old_rl_v; plane_start[p]=old_ps_v;
continue;
}
gen_plane(p);
long long ns=eval_score_diff(p);
long long d=ns-cur_score;
bool accept=(d>=0);
if(!accept && cur_temp>0){
accept=((rng()%1000000)<(int)(exp((double)d/cur_temp)*1000000));
}
if(accept){
cur_score=ns;
if(ns>best_score){
best_score=ns;
for(int q=1;q<=K;q++){
memcpy(best_rd[q],rd[q],sizeof(int)*rl[q]);
best_rl[q]=rl[q]; best_ps[q]=plane_start[q];
}
}
} else {
memcpy(rd[p],old_rd_buf,sizeof(int)*old_rl_v);
rl[p]=old_rl_v; plane_start[p]=old_ps_v;
pfl_cnt[p]=old_pfl_cnt_v;
memcpy(pfl[p],old_pfl_buf,sizeof(Flight)*old_pfl_cnt_v);
}
}
}
for(int p=1;p<=K;p++){
memcpy(rd[p],best_rd[p],sizeof(int)*best_rl[p]);
rl[p]=best_rl[p]; plane_start[p]=best_ps[p];
gen_plane(p);
}
fprintf(stderr,"SA: %d iters, best=%lld\n",iter,best_score);
for(int p=1;p<=K;p++){
printf("%d\n",pfl_cnt[p]);
for(int i=0;i<pfl_cnt[p];i++)
printf("%d %02d:%02d %d %02d:%02d\n",
pfl[p][i].a,pfl[p][i].s/60,pfl[p][i].s%60,
pfl[p][i].b,pfl[p][i].t/60,pfl[p][i].t%60);
}
return 0;
}