結果
| 問題 |
No.5016 Worst Mayor
|
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2023-04-29 15:25:51 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,822 bytes |
| コンパイル時間 | 3,427 ms |
| コンパイル使用メモリ | 242,980 KB |
| 実行使用メモリ | 206,176 KB |
| スコア | 18,269,071,291 |
| 平均クエリ数 | 384.00 |
| 最終ジャッジ日時 | 2023-04-29 15:27:30 |
| 合計ジャッジ時間 | 95,956 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 49 TLE * 1 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
template<class T> void chmin(T &a,T b){
if(a>b){
a=b;
}
}
template<class T> void chmax(T &a,T b){
if(a<b){
a=b;
}
}
vector<int> pi={0,1,0,-1},pj={1,0,-1,0};
int to(int i,int j){
return i*14+j;
}
pii back(int x){
return {x/14,x%14};
}
struct input{
int n,t;
vector<int> s,g;
void input_cin(){
cin >> n >> t;
s.resize(n);
g.resize(n);
rep(i,n){
int a,b,c,d;
cin >> a >> b >> c >> d;
a--;
b--;
c--;
d--;
s[i]=to(a,b);
g[i]=to(c,d);
}
}
}input;
struct solver{
vector<vector<int>> people;
vector<vector<int>> root(vector<vector<pii>> &g){
vector<vector<int>> ret(14*14,vector<int>(14*14,0));
rep(i,14*14){
vector<int> dist(14*14,INF);
vector<int> prev(14*14);
priority_queue<pii> pq;
dist[i]=0;
pq.push({i,i});
while(!pq.empty()){
int x,d;
tie(x,d)=pq.top();
pq.pop();
for(auto &[to,w]:g[x]){
if(dist[x]+w<dist[to]){
dist[to]=dist[x]+w;
prev[to]=x;
pq.push({to,dist[x]+w});
}
}
}
rep(j,14*14){
if(people[i][j]==0) continue;
int now=j;
while(now!=i){
ret[prev[now]][now]++;
now=prev[now];
}
}
}
return ret;
}
int score(vector<vector<pii>> &g){
int ret=0;
rep(i,14*14){
vector<int> dist(14*14,INF);
vector<int> prev(14*14);
priority_queue<pii> pq;
dist[i]=0;
pq.push({i,i});
while(!pq.empty()){
int x,d;
tie(x,d)=pq.top();
pq.pop();
for(auto &[to,w]:g[x]){
if(dist[x]+w<dist[to]){
dist[to]=dist[x]+w;
prev[to]=x;
pq.push({to,dist[x]+w});
}
}
}
rep(j,14*14){
if(people[i][j]==0) continue;
int now=j,cnt=0;
while(now!=i){
if(dist[now]-dist[prev[now]]==223) cnt++;
now=prev[now];
}
ret+=60*cnt*people[i][j];
}
}
return ret;
}
void solve(){
vector<vector<pii>> g(14*14);
rep(i,14){
rep(j,14){
rep(k,4){
int ti=i+pi[k],tj=j+pj[k];
if(ti<0||14<=ti||tj<0||14<=tj) continue;
g[to(i,j)].emplace_back(to(ti,tj),1000);
}
}
}
people.resize(14*14);
rep(i,14*14) people[i].resize(14*14,0);
rep(i,input.n){
people[input.s[i]][input.g[i]]++;
}
int x=70;
vector<int> score_sum(x+1,0);
vector<pii> v(x);
vector<vector<bool>> built(14*14,vector<bool>(14*14,false));
int ns=-1,ng=-1;
rep(r,x){
vector<vector<int>> cnt=root(g);
int max_cnt=0,ts=-1,tg=-1;
rep(i,14*14){
rep(j,14*14){
if(cnt[i][j]==0) continue;
if(built[i][j]) continue;
if(max_cnt<cnt[i][j]){
max_cnt=cnt[i][j];
ts=i;
tg=j;
}
}
}
if(ts==-1||tg==-1) break;
for(auto &[to,w]:g[ts]){
if(to==tg) w=223;
}
for(auto &[to,w]:g[tg]){
if(to==ts) w=223;
}
score_sum[r+1]=score(g);
ns=ts;
ng=tg;
built[ns][ng]=true;
built[ng][ns]=true;
v[r]={ns,ng};
}
vector<vector<vector<int>>> dp(input.t+1,vector<vector<int>>(input.t+1,vector<int>(x,-INF)));
vector<vector<vector<tii>>> prev(input.t+1,vector<vector<tii>>(input.t+1,vector<tii>(x)));
dp[0][1][0]=1e6;
rep(i,input.t){
rep(j,input.t+1){
rep(k,x){
if(dp[i][j][k]==-INF) continue;
if(0<j&&k+1<x){
int cost=1e7/sqrt(j);
if(cost<=dp[i][j][k]&&dp[i+1][j][k+1]<dp[i][j][k]-cost+score_sum[k+1]){
dp[i+1][j][k+1]=dp[i][j][k]-cost+score_sum[k];
prev[i+1][j][k+1]={i,j,k};
}
}
if(j+1<input.t){
if(dp[i+1][j+1][k]<dp[i][j][k]+score_sum[k]){
dp[i+1][j+1][k]=dp[i][j][k]+score_sum[k];
prev[i+1][j+1][k]={i,j,k};
}
}
if(dp[i+1][j][k]<dp[i][j][k]+50000+score_sum[k]){
dp[i+1][j][k]=dp[i][j][k]+50000+score_sum[k];
prev[i+1][j][k]={i,j,k};
}
}
}
}
int max_score=-INF,ni=input.t,nj=-1,nk=-1;
rep(i,input.t+1){
rep(j,x){
if(max_score<dp[input.t][i][j]){
max_score=dp[input.t][i][j];
nj=i;
nk=j;
}
}
}
vector<int> ans;
while(ni!=0){
int ti,tj,tk;
tie(ti,tj,tk)=prev[ni][nj][nk];
if(tk!=nk){
ans.push_back(0);
}else if(tj!=nj){
ans.push_back(1);
}else{
ans.push_back(2);
}
ni=ti;
nj=tj;
nk=tk;
}
reverse(all(ans));
int now=0;
rep(i,input.t){
int cin_u,cin_v;
cin >> cin_u >> cin_v;
if(ans[i]==0){
int s,t;
tie(s,t)=v[now];
int o,p,q,r;
tie(o,p)=back(s);
tie(q,r)=back(t);
cout << ans[i]+1 << " " << o+1 << " " << p+1 << " " << q+1 << " " << r+1 << endl;
now++;
}else{
cout << ans[i]+1 << endl;
}
}
}
}solver;
int main(){
input.input_cin();
solver.solve();
}