結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-02-27 07:35:49 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 817 ms / 1,000 ms |
| コード長 | 17,619 bytes |
| 記録 | |
| コンパイル時間 | 8,760 ms |
| コンパイル使用メモリ | 424,816 KB |
| 実行使用メモリ | 15,984 KB |
| スコア | 62,947,632 |
| 最終ジャッジ日時 | 2026-02-27 07:37:23 |
| 合計ジャッジ時間 | 91,194 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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,T=181,Target_size=21;
array<int,N> X,Y,W;
array<array<ll,N>,N> W_score;
ll W_score_sum=0;
struct Plan{
int a,b;
int s,t;
auto operator<=>(const Plan &other) const{
return this->t<=>other.t;
}
};
array<Plan,M> P;
array<array<int,N>,N> D;
array<array<bool,N>,N> Is_target;
array<string,T> Time_string;
array<int,Target_size> Target_times;
namespace Solver{
void calc_times(int j,int t,const vector<Plan> &sorted_plans,array<int,N> &s){
s.fill(-INF);
s[j]=t;
for(const auto &plan:sorted_plans){
if(plan.t<=s[plan.b]&&s[plan.a]<plan.s){
s[plan.a]=plan.s;
}
}
}
array<array<int,N>,Target_size*N> memo_s_sq;
array<vector<int>,N> square_t_plans;
array<array<bool,Target_size>,N> square_next_update;
struct Candidate{
ll score=0;
int n=-1;
int parent=-1;
auto operator<=>(const Candidate &other) const{
return this->score<=>other.score;
}
};
struct State{
array<vector<Plan>,K> ans;
vector<Plan> plans;
ll calc_now_ci(int j,const auto &s_sq,const auto &s_ci){
int sum=0;
rep(i,N){
sum+=Is_target[j][i]*W[i]*(s_sq[i]<s_ci[i]);
}
return (ll)sum*W[j];
}
ll calc_true_score(){
sort(all(plans));
reverse(all(plans));
array<vector<int>,N> circle_t_plans;
for(auto plan:plans){
circle_t_plans[plan.b].push_back(plan.t);
}
rep(i,N) sort(all(circle_t_plans[i]));
array<array<bool,21>,N> circle_next_update;
rep(j,N){
circle_next_update[j].fill(false);
rep(t_idx,len(Target_times)-1){
auto itr_circle=upper_bound(all(circle_t_plans[j]),Target_times[t_idx]);
if(itr_circle!=circle_t_plans[j].end()&&*itr_circle<=Target_times[t_idx+1]){
circle_next_update[j][t_idx]=true;
}
}
}
ll ci=0;
for(int j=0;j<N;j++){
array<int,N> s_ci;
calc_times(j,Target_times.front(),plans,s_ci);
auto s_sq=memo_s_sq[j*Target_size];
ll now_ci=calc_now_ci(j,s_sq,s_ci);
rep(t_idx,len(Target_times)){
ci+=now_ci;
if(t_idx+1<len(Target_times)){
bool update=false;
if(square_next_update[j][t_idx]){
s_sq=memo_s_sq[j*Target_size+t_idx+1];
update=true;
}
if(circle_next_update[j][t_idx]){
calc_times(j,Target_times[t_idx+1],plans,s_ci);
update=true;
}
if(update){
now_ci=calc_now_ci(j,s_sq,s_ci);
}
}
}
}
return ci;
}
int k=0;
ll score=0;
auto operator<=>(const State &other) const{
return this->score<=>other.score;
}
array<array<ll,N>,T> dp;
array<array<pii,N>,T> pre;
vector<Candidate> get_candidates(int parent){
sort(all(plans));
reverse(all(plans));
array<vector<int>,N> circle_t_plans;
for(auto plan:plans){
circle_t_plans[plan.b].push_back(plan.t);
}
rep(i,N) sort(all(circle_t_plans[i]));
array<array<bool,Target_size>,N> circle_next_update;
rep(j,N){
circle_next_update[j].fill(false);
rep(t_idx,len(Target_times)){
auto itr_circle=upper_bound(all(circle_t_plans[j]),Target_times[t_idx]);
if(itr_circle!=circle_t_plans[j].end()&&*itr_circle<=Target_times[t_idx+1]){
circle_next_update[j][t_idx]=true;
}
}
}
array<array<array<ll,T+1>,N>,N> point;
rep(j,N){
rep(i,N){
point[j][i].fill(0);
}
}
for(int j=0;j<N;j++){
array<int,N> s_ci;
calc_times(j,Target_times.front(),plans,s_ci);
auto s_sq=memo_s_sq[j*Target_size];
rep(t_idx,len(Target_times)){
int t=Target_times[t_idx];
rep(i,N){
if(s_sq[i]<s_ci[i]) continue;
if(!Is_target[j][i]) continue;
rep(c,N){
if(c==i) continue;
int l=clamp(s_sq[i]+1+D[i][c],0,T+1);
int r=s_ci[c];
if(c==j) r=t;
if(r<=l) continue;
point[c][i][l]+=W_score[j][i];
point[c][i][r+1]-=W_score[j][i];
}
}
if(t_idx+1<len(Target_times)){
if(square_next_update[j][t_idx]){
s_sq=memo_s_sq[j*Target_size+t_idx+1];
}
if(circle_next_update[j][t_idx]){
calc_times(j,Target_times[t_idx+1],plans,s_ci);
}
}
}
}
rep(j,N){
rep(i,N){
rep(t,T){
point[j][i][t+1]+=point[j][i][t];
}
}
}
rep(t,T){
dp[t].fill(0);
pre[t].fill({-1,-1});
}
for(int t=T-1;0<=t;t--){
rep(j,N){
if(dp[t][j]<0) continue;
if(0<=t-1){
if(chmax(dp[t-1][j],dp[t][j])) pre[t-1][j]={t,j};
}
rep(i,N){
if(i==j) continue;
int s=t-D[j][i];
if(0<=s){
if(chmax(dp[s][i],dp[t][j]+point[j][i][t])) pre[s][i]={t,j};
}
}
}
}
vector<Candidate> ret;
rep(n,N){
ll now=0;
for(int t=T-1;0<=t;t--){
chmax(now,dp[t][n]);
}
ret.emplace_back(score+now,n,parent);
}
sort(all(ret));
reverse(all(ret));
ret.resize(3);
return ret;
}
void advance(Candidate candidate){
int nt=-1,ni=-1;
ll best_point=-INF_ll;
for(int t=T-1;0<=t;t--){
if(chmax(best_point,dp[t][candidate.n])){
nt=t;
ni=candidate.n;
}
}
while(true){
auto [pt,pi]=pre[nt][ni];
if(pt==-1) break;
if(ni!=pi){
ans[k].emplace_back(ni,pi,nt,pt);
plans.emplace_back(ni,pi,nt,pt);
}
nt=pt;
ni=pi;
}
score=calc_true_score();
k++;
}
};
auto beam_search(){
constexpr int W=5;
vector<State> dp;
dp.push_back(State());
rep(k,K){
//cerr << dp[0].score << " " << len(dp) << endl;
vector<State> new_dp;
rep(w,W){
if(len(dp)<=w) break;
vector<Candidate> candidates=dp[w].get_candidates(w);
for(auto candidate:candidates){
State state=dp[w];
state.advance(candidate);
new_dp.push_back(state);
}
}
sort(all(new_dp));
reverse(all(new_dp));
if(W<len(new_dp)) new_dp.resize(W);
swap(dp,new_dp);
}
assert(!dp.empty());
return dp[0].ans;
}
void solve(){
vector<Plan> plans(all(P));
sort(all(plans));
reverse(all(plans));
rep(j,N){
rep(t_idx,Target_size){
calc_times(j,Target_times[t_idx],plans,memo_s_sq[j*Target_size+t_idx]);
}
}
rep(i,M){
square_t_plans[P[i].b].push_back(P[i].t);
}
rep(i,N) sort(all(square_t_plans[i]));
rep(j,N){
square_next_update[j].fill(false);
rep(t_idx,len(Target_times)){
auto itr_square=upper_bound(all(square_t_plans[j]),Target_times[t_idx]);
if(itr_square!=square_t_plans[j].end()&&*itr_square<=Target_times[t_idx+1]){
square_next_update[j][t_idx]=true;
}
}
}
array<vector<Plan>,K> ans=beam_search();
rep(k,K){
cout << len(ans[k]) << '\n';
rep(i,len(ans[k])){
if(1<=i){
assert(ans[k][i-1].b==ans[k][i].a);
assert(ans[k][i-1].t<=ans[k][i].s);
}
assert(0<=ans[k][i].s&&ans[k][i].s<T);
assert(0<=ans[k][i].t&&ans[k][i].t<T);
assert(ans[k][i].t-ans[k][i].s==D[ans[k][i].a][ans[k][i].b]);
}
for(auto plan:ans[k]){
cout << plan.a+1 << ' ' << Time_string[plan.s] << ' ' << plan.b+1 << ' ' << Time_string[plan.t] << '\n';
}
}
cerr << Timer::get_ms_all_program() << ' ' << endl;
}
}
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-6*60)/5;
P[i].t=(tx*60+ty-6*60)/5;
}
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/5;
}
}
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-6*60)/5]=sx+":"+sy;
if(i==21) break;
}
}
int idx=0;
for(int i=11;i<=21;i++){
for(int j=0;j<60;j+=30){
Target_times[idx]=(i*60+j-6*60)/5;
idx++;
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;
}
}
}
rep(i,N){
W_score[i].fill(0);
rep(j,N){
if(Is_target[i][j]) W_score[i][j]=(ll)W[i]*W[j];
}
}
W_score_sum=0;
rep(i,N){
rep(j,N){
if(!Is_target[i][j]) continue;
rep(_,len(Target_times)){
W_score_sum+=W_score[i][j];
}
}
}
Solver::solve();
exit(0);
}