結果

問題 No.5016 Worst Mayor
ユーザー FplusFplusFFplusFplusF
提出日時 2023-04-29 15:06:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,372 ms / 2,000 ms
コード長 6,844 bytes
コンパイル時間 4,419 ms
コンパイル使用メモリ 242,532 KB
実行使用メモリ 155,784 KB
スコア 7,458,233,624
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 15:07:46
合計ジャッジ時間 64,260 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,223 ms
155,168 KB
testcase_01 AC 1,224 ms
155,152 KB
testcase_02 AC 1,161 ms
155,168 KB
testcase_03 AC 1,265 ms
155,420 KB
testcase_04 AC 1,133 ms
155,412 KB
testcase_05 AC 1,197 ms
155,240 KB
testcase_06 AC 1,189 ms
155,296 KB
testcase_07 AC 1,343 ms
154,780 KB
testcase_08 AC 989 ms
155,248 KB
testcase_09 AC 955 ms
155,244 KB
testcase_10 AC 1,127 ms
155,148 KB
testcase_11 AC 1,321 ms
155,244 KB
testcase_12 AC 960 ms
155,372 KB
testcase_13 AC 1,309 ms
155,056 KB
testcase_14 AC 1,158 ms
155,332 KB
testcase_15 AC 1,110 ms
154,852 KB
testcase_16 AC 1,021 ms
155,372 KB
testcase_17 AC 892 ms
155,496 KB
testcase_18 AC 885 ms
154,960 KB
testcase_19 AC 986 ms
154,868 KB
testcase_20 AC 1,174 ms
154,992 KB
testcase_21 AC 950 ms
155,300 KB
testcase_22 AC 1,246 ms
155,288 KB
testcase_23 AC 867 ms
155,376 KB
testcase_24 AC 1,152 ms
155,268 KB
testcase_25 AC 1,273 ms
154,948 KB
testcase_26 AC 1,299 ms
155,256 KB
testcase_27 AC 1,035 ms
155,536 KB
testcase_28 AC 948 ms
155,420 KB
testcase_29 AC 1,138 ms
155,524 KB
testcase_30 AC 1,236 ms
155,784 KB
testcase_31 AC 1,265 ms
155,152 KB
testcase_32 AC 1,229 ms
155,396 KB
testcase_33 AC 1,144 ms
154,992 KB
testcase_34 AC 1,219 ms
154,968 KB
testcase_35 AC 1,064 ms
155,460 KB
testcase_36 AC 1,087 ms
154,940 KB
testcase_37 AC 1,168 ms
155,096 KB
testcase_38 AC 1,222 ms
155,152 KB
testcase_39 AC 1,328 ms
154,864 KB
testcase_40 AC 1,318 ms
155,516 KB
testcase_41 AC 1,372 ms
154,912 KB
testcase_42 AC 1,352 ms
154,996 KB
testcase_43 AC 1,081 ms
155,152 KB
testcase_44 AC 1,137 ms
154,864 KB
testcase_45 AC 1,133 ms
155,176 KB
testcase_46 AC 860 ms
155,404 KB
testcase_47 AC 1,197 ms
154,956 KB
testcase_48 AC 1,066 ms
154,956 KB
testcase_49 AC 972 ms
154,960 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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=min<int>(50,50);
        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][0][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][0][k+1]<dp[i][j][k]-cost+score_sum[k+1]){
                            dp[i+1][0][k+1]=dp[i][j][k]-cost+score_sum[k];
                            prev[i+1][0][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();
}
0