結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-02-25 23:32:57 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 923 ms / 1,000 ms |
| コード長 | 11,761 bytes |
| 記録 | |
| コンパイル時間 | 5,549 ms |
| コンパイル使用メモリ | 369,788 KB |
| 実行使用メモリ | 7,844 KB |
| スコア | 41,470,792 |
| 最終ジャッジ日時 | 2026-02-25 23:35:10 |
| 合計ジャッジ時間 | 101,900 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge7 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,const T &b){
if(a>b){
a=b;
return true;
}
return false;
}
template<class T> inline bool chmax(T &a,const T &b){
if(a<b){
a=b;
return true;
}
return false;
}
namespace Timer{
chrono::steady_clock::time_point program_start,start;
void program_start_snap(){
program_start=start=chrono::steady_clock::now();
}
void snap(){
start=chrono::steady_clock::now();
}
int get_ms(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
return ms;
}
int get_ms_all_program(){
auto now=chrono::steady_clock::now();
int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
return ms;
}
}
mt19937 mt;
uint32_t rand_int(uint32_t r){ //[0,r)
assert(r!=0);
return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){ //[l,r)
assert(l<r);
return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){ //[0.0,1.0]
return mt()*one_div_mt_max;
}
template<class T> T get_random_element(const vector<T> &v){
assert(!v.empty());
return v[rand_int(len(v))];
}
template<class T> void add(vector<T> &a,vector<T> b){
for(auto i:b) a.push_back(i);
}
template<class SA_State,int limit_ms,double start_temp,double end_temp=0.0> SA_State SA(const SA_State &first_state){
SA_State state=first_state,best_state=state;
int loop_cnt=0,accept_cnt=0,update_cnt=0;
int ms=0;
double temp=start_temp;
Timer::snap();
while(true){
if(true){
ms=Timer::get_ms();
if(limit_ms<=ms) break;
//double t=(double)ms/limit_ms;
temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
//temp=pow(start_temp,1-t)*pow(end_temp,t);
}
loop_cnt++;
double accept_diff=log(rand_double())*temp;
bool accepted=state.modify(accept_diff);
if(accepted){
accept_cnt++;
if(best_state.score<state.score){
best_state=state;
cerr << "score:" << (int)best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
update_cnt++;
}
}
}
cerr << "[result] " << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
return best_state;
};
constexpr int N=47,R=1000,M=400,K=25;
array<int,N> X,Y,W;
struct Plan{
int a,b;
int s,t;
int idx=-1;
};
array<Plan,M> P;
array<array<int,N>,N> D;
array<array<bool,N>,N> Is_target;
map<int,string> Time_string;
vector<int> Target_times;
namespace Solver{
auto calc_times(int j,int t,const array<vector<Plan>,N> &g){
array<int,N> s,vis;
s.fill(-INF);
s[j]=t;
vis.fill(false);
priority_queue<pii> pq;
pq.push({t,j});
while(!pq.empty()){
auto [nt,x]=pq.top();
pq.pop();
if(vis[x]) continue;
vis[x]=true;
for(auto plan:g[x]){
assert(plan.b==x);
if(s[x]<plan.t) continue;
if(vis[plan.a]) continue;
if(s[plan.a]<plan.s){
s[plan.a]=plan.s;
pq.push({plan.s,plan.a});
}
}
}
return s;
}
map<pii,array<int,N>> memo_s_sq;
int calc_score(const array<vector<Plan>,K> &ans){
array<vector<Plan>,N> rev_circle;
rep(i,K){
for(auto plan:ans[i]){
rev_circle[plan.b].push_back(plan);
}
}
ll sq=0,ci=0;
vector<int> ord(N);
rep(i,N) ord[i]=i;
sort(all(ord),[&](int i,int j){return W[i]>W[j];});
ord.resize(N/3*2);
for(auto j:ord){
for(auto t:Target_times){
auto s_sq=memo_s_sq[{j,t}];
auto s_ci=calc_times(j,t,rev_circle);
rep(i,N){
if(!Is_target[i][j]) continue;
if(s_sq[i]<s_ci[i]) ci+=(ll)W[i]*W[j];
else sq+=(ll)W[i]*W[j];
}
}
}
return floor(1e6*ci/((double)sq+ci));
}
array<vector<Plan>,N> rev_square;
struct State{
set<int> vis;
array<vector<Plan>,K> ans;
int score=0;
State(auto ans_):ans(ans_){
rep(k,K){
int x=rand_int(N),t=21*60;
while(true){
vector<int> v;
rep(i,N){
if(i==x) continue;
if(t-D[x][i]<6*60) continue;
v.push_back(i);
}
if(v.empty()) break;
set<int> st(all(v));
int nx=-1,best_t=-INF;
Plan best_plan;
for(auto plan:rev_square[x]){
if(t<=plan.t) continue;
if(vis.contains(plan.idx)) continue;
if(st.contains(plan.a)&&chmax(best_t,plan.t)){
nx=plan.a;
best_plan=plan;
}
}
if(nx==-1){
nx=get_random_element(v);
}else{
vis.insert(best_plan.idx);
}
ans[k].emplace_back(nx,x,t-D[x][nx],t);
t-=D[nx][x];
x=nx;
}
reverse(all(ans[k]));
}
score=calc_score(ans);
}
bool modify(double accept_diff){
auto new_ans=ans;
int k=rand_int(K);
new_ans[k].clear();
auto new_vis=vis;
for(auto plan:ans[k]){
new_vis.erase(plan.idx);
}
int x=rand_int(N),t=21*60;
while(true){
vector<int> v;
rep(i,N){
if(i==x) continue;
if(t-D[x][i]<6*60) continue;
v.push_back(i);
}
if(v.empty()) break;
set<int> st(all(v));
int nx=-1,best_t=-INF;
Plan best_plan;
for(auto plan:rev_square[x]){
if(t<=plan.t) continue;
if(new_vis.contains(plan.idx)) continue;
if(st.contains(plan.a)&&chmax(best_t,plan.t+rand_int(100,200))){
nx=plan.a;
best_plan=plan;
}
}
if(nx==-1){
nx=get_random_element(v);
}else{
new_vis.insert(best_plan.idx);
}
new_ans[k].emplace_back(nx,x,t-D[x][nx],t,best_plan.idx);
t-=D[nx][x];
x=nx;
}
reverse(all(new_ans[k]));
int new_score=calc_score(new_ans);
if(accept_diff<=new_score-score){
score=new_score;
ans=new_ans;
vis=new_vis;
return true;
}
return false;
}
};
void solve(){
rep(i,M){
rev_square[P[i].b].push_back(P[i]);
}
rep(j,N){
for(auto t:Target_times){
memo_s_sq[{j,t}]=calc_times(j,t,rev_square);
}
}
array<vector<Plan>,K> ans;
State state(ans);
state=SA<State,900,0.0,0.0>(state);
ans=state.ans;
cerr << calc_score(ans) << endl;
rep(k,K){
cout << len(ans[k]) << '\n';
for(auto plan:ans[k]){
cout << plan.a+1 << ' ' << Time_string[plan.s] << ' ' << plan.b+1 << ' ' << Time_string[plan.t] << '\n';
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Timer::program_start_snap();
int n,r;
cin >> n >> r;
assert(n==N);
assert(r==R);
rep(i,N) cin >> X[i] >> Y[i] >> W[i];
int m;
cin >> m;
assert(m==M);
rep(i,M){
int a,b;
string s,t;
cin >> a >> s >> b >> t;
a--;
b--;
P[i].a=a;
P[i].b=b;
int sx=stoi(s.substr(0,2)),sy=stoi(s.substr(3,2));
int tx=stoi(t.substr(0,2)),ty=stoi(t.substr(3,2));
P[i].s=sx*60+sy;
P[i].t=tx*60+ty;
P[i].idx=i;
}
int k;
cin >> k;
assert(k==K);
rep(i,N){
rep(j,N){
double d=hypot<double>(X[i]-X[j],Y[i]-Y[j]);
int t=ceil(60*d/800+40);
while(t%5!=0) t++;
D[i][j]=t;
}
}
for(int i=6;i<=21;i++){
for(int j=0;j<60;j+=5){
string sx=to_string(i),sy=to_string(j);
while(len(sx)<2) sx.insert(sx.begin(),'0');
while(len(sy)<2) sy.insert(sy.begin(),'0');
Time_string[i*60+j]=sx+":"+sy;
if(i==21) break;
}
}
for(int i=11;i<=21;i++){
Target_times.push_back(i*60);
if(i==21) break;
}
rep(i,N){
rep(j,N){
ll x=((ll)(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]))*16;
if(R*R<=x){
Is_target[i][j]=true;
}else{
Is_target[i][j]=false;
}
}
}
Solver::solve();
exit(0);
}