結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-02-26 22:31:53 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 965 ms / 1,000 ms |
| コード長 | 13,549 bytes |
| 記録 | |
| コンパイル時間 | 6,240 ms |
| コンパイル使用メモリ | 365,352 KB |
| 実行使用メモリ | 7,844 KB |
| スコア | 55,033,772 |
| 最終ジャッジ日時 | 2026-02-26 22:33:42 |
| 合計ジャッジ時間 | 107,415 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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;
array<array<ll,N>,N> W_score;
ll W_score_sum=0;
struct Plan{
int a,b;
int s,t;
int idx=-1;
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;
map<int,string> Time_string;
vector<int> 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>,21*N> memo_s_sq;
auto tours_to_ans(array<vector<int>,K> tours){
array<vector<Plan>,K> ans;
rep(k,K){
if(tours.empty()) continue;
int x=tours[k].back(),t=21*60;
tours[k].pop_back();
while(!tours[k].empty()){
int y=tours[k].back();
if(t-D[y][x]<6*60) break;
if(x==y){
tours[k].pop_back();
continue;
}
ans[k].emplace_back(y,x,t-D[y][x],t);
t-=D[y][x];
x=y;
tours[k].pop_back();
}
reverse(all(ans[k]));
}
return ans;
}
array<vector<int>,N> square_t_plans;
ll calc_now_ci(int j,const auto &s_sq,const auto &s_ci){
ll now_ci=0;
rep(i,N){
if(!Is_target[i][j]) continue;
now_ci+=W_score[i][j]*(s_sq[i]<s_ci[i]);
}
return now_ci;
}
int calc_score(const array<vector<int>,K> &tours,int kr=K){
auto ans=tours_to_ans(tours);
vector<Plan> plans;
rep(i,kr){
for(auto plan:ans[i]){
plans.push_back(plan);
}
}
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]));
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*21+(Target_times.front()-11*60)/30];
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)){
int t=Target_times[t_idx];
bool update=false;
auto itr_square=upper_bound(all(square_t_plans[j]),t);
if(itr_square!=square_t_plans[j].end()&&*itr_square<=Target_times[t_idx+1]){
s_sq=memo_s_sq[j*21+(Target_times[t_idx+1]-11*60)/30];
update=true;
}
auto itr_circle=upper_bound(all(circle_t_plans[j]),t);
if(itr_circle!=circle_t_plans[j].end()&&*itr_circle<=Target_times[t_idx+1]){
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);
}
}
}
}
ll sq=W_score_sum-ci;
return floor(1e6*(double)ci/(sq+ci));
}
vector<int> w_sum;
int get_random_city(){
return upper_bound(all(w_sum),rand_int(w_sum.back()))-w_sum.begin()-1;
}
void update_tour(vector<int> &tour){
if(tour.empty()) tour.push_back(get_random_city());
int x=tour.back(),t=21*60;
tour.pop_back();
vector<int> new_tour;
new_tour.push_back(x);
while(true){
int y=-1;
if(tour.empty()){
y=get_random_city();
}else{
y=tour.back();
tour.pop_back();
}
if(x==y) continue;
if(t-D[y][x]<6*60) break;
new_tour.push_back(y);
t-=D[y][x];
x=y;
}
reverse(all(new_tour));
tour=new_tour;
}
struct State{
set<int> vis;
array<vector<int>,K> tours;
int score=0;
int k=0;
State(){
rep(k,K){
update_tour(tours[k]);
}
score=0;
}
bool modify(double accept_diff){
auto new_tours=tours;
int r=rand_int(4);
int sz=len(new_tours[k]);
if(r==0){
new_tours[k].insert(new_tours[k].begin()+rand_int(sz+1),get_random_city());
}else if(r==1){
if(new_tours[k].empty()) return false;
new_tours[k].erase(new_tours[k].begin()+rand_int(sz));
}else if(r==2){
if(new_tours[k].empty()) return false;
new_tours[k][rand_int(sz)]=get_random_city();
}else{
swap(new_tours[k][rand_int(sz)],new_tours[k][rand_int(sz)]);
}
update_tour(new_tours[k]);
int new_score=calc_score(new_tours,k+1);
if(accept_diff<=new_score-score){
score=new_score;
tours=new_tours;
return true;
}
return false;
}
};
void solve(){
w_sum.resize(N+1,0);
rep(i,N) w_sum[i+1]=w_sum[i]+W[i];
vector<Plan> plans(all(P));
sort(all(plans));
reverse(all(plans));
rep(j,N){
for(auto t:Target_times){
calc_times(j,t,plans,memo_s_sq[j*21+(t-11*60)/30]);
}
}
rep(i,M){
square_t_plans[P[i].b].push_back(P[i].t);
}
rep(i,N) sort(all(square_t_plans[i]));
array<vector<Plan>,K> ans;
State state;
rep(k,K){
state.k=k;
state=SA<State,950/K,1000.0,0.0>(state);
}
ans=tours_to_ans(state.tours);
cerr << calc_score(state.tours) << endl;
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(Time_string.contains(ans[k][i].s));
assert(Time_string.contains(ans[k][i].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';
}
}
}
}
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++){
for(int j=0;j<60;j+=30){
Target_times.push_back(i*60+j);
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){
rep(j,N){
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);
}