#776489 (C++14) No.1069 電柱 / Pole (Hard)

提出ソース

結果

問題	No.1069 電柱 / Pole (Hard)
ユーザー	bin101
提出日時	2022-07-07 02:42:05
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	112 ms / 2,000 ms
コード長	16,910 bytes
コンパイル時間	3,306 ms
コンパイル使用メモリ	229,208 KB
実行使用メモリ	15,360 KB
最終ジャッジ日時	2024-07-23 15:10:22
合計ジャッジ時間	5,656 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	112 ms 7,808 KB
testcase_05	AC	89 ms 15,360 KB
testcase_06	AC	5 ms 6,940 KB
testcase_07	AC	6 ms 6,940 KB
testcase_08	AC	4 ms 6,940 KB
testcase_09	AC	5 ms 6,940 KB
testcase_10	AC	4 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	4 ms 6,940 KB
testcase_14	AC	3 ms 6,940 KB
testcase_15	AC	3 ms 6,944 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	3 ms 6,940 KB
testcase_18	AC	3 ms 6,940 KB
testcase_19	AC	5 ms 6,940 KB
testcase_20	AC	3 ms 6,944 KB
testcase_21	AC	3 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	7 ms 6,940 KB
testcase_24	AC	5 ms 6,940 KB
testcase_25	AC	6 ms 6,944 KB
testcase_26	AC	5 ms 6,940 KB
testcase_27	AC	5 ms 6,944 KB
testcase_28	AC	5 ms 6,944 KB
testcase_29	AC	3 ms 6,944 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,944 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	3 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,944 KB
testcase_41	AC	3 ms 6,940 KB
testcase_42	AC	3 ms 6,940 KB
testcase_43	AC	2 ms 6,940 KB
testcase_44	AC	4 ms 6,940 KB
testcase_45	AC	3 ms 6,944 KB
testcase_46	AC	4 ms 6,940 KB
testcase_47	AC	4 ms 6,944 KB
testcase_48	AC	5 ms 6,940 KB
testcase_49	AC	4 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	4 ms 6,940 KB
testcase_52	AC	2 ms 6,944 KB
testcase_53	AC	4 ms 6,944 KB
testcase_54	AC	2 ms 6,944 KB
testcase_55	AC	2 ms 6,944 KB
testcase_56	AC	2 ms 6,940 KB
testcase_57	AC	2 ms 6,944 KB
testcase_58	AC	2 ms 6,940 KB
testcase_59	AC	2 ms 6,940 KB
testcase_60	AC	2 ms 6,940 KB
testcase_61	AC	2 ms 6,940 KB
testcase_62	AC	2 ms 6,944 KB
testcase_63	AC	2 ms 6,944 KB
testcase_64	AC	2 ms 6,944 KB
testcase_65	AC	2 ms 6,940 KB
testcase_66	AC	2 ms 6,944 KB
testcase_67	AC	2 ms 6,944 KB
testcase_68	AC	2 ms 6,940 KB
testcase_69	AC	3 ms 6,944 KB
testcase_70	AC	3 ms 6,944 KB
testcase_71	AC	3 ms 6,940 KB
testcase_72	AC	2 ms 6,940 KB
testcase_73	AC	2 ms 6,944 KB
testcase_74	AC	3 ms 6,940 KB
testcase_75	AC	4 ms 6,944 KB
testcase_76	AC	5 ms 6,940 KB
testcase_77	AC	5 ms 6,944 KB
testcase_78	AC	2 ms 6,944 KB
testcase_79	AC	4 ms 6,940 KB
testcase_80	AC	5 ms 6,940 KB
testcase_81	AC	3 ms 6,940 KB
testcase_82	AC	4 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h> 
using namespace std;
using ll=long long int;
//using Int=__int128;
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> constexpr int bitUP(T x,int a){return (x>>a)&1;}
//→　↓　←　↑ 
int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0};
//右上から時計回り
//int dh[8]={-1,0,1,1,1,0,-1,-1}, dw[8]={1,1,1,0,-1,-1,-1,0};
long double EPS = 1e-6;
long double PI = acos(-1);
const ll INF=(1LL<<62);
const int MAX=(1<<30);
//constexpr ll MOD=1000000000+7;
constexpr ll MOD=998244353;


inline void bin101(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
}

using pii=pair<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;

using Graph=vector<vector<int>>;

template<typename T >
struct edge {
	int to;
	T cost;
	edge()=default;
	edge(int to, T cost) : to(to), cost(cost) {}

};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;

template<typename T>
void CinGraph(int M,WeightGraph<T> &g,bool directed=false,bool index1=true){
    while(M--){
        int s,t;
        T cost;
        cin>>s>>t>>cost;
        if(index1) s--,t--;
        g[s].emplace_back(t,cost);
        if(not directed) g[t].emplace_back(s,cost);
    }
}

void CinGraph(int M,Graph &g,bool directed=false,bool index1=true){
    while(M--){
        int s,t;
        cin>>s>>t;
        if(index1) s--,t--;
        g[s].push_back(t);
        if(not directed) g[t].push_back(s);
    }
}


//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<T> &v) {
    for(size_t i=0;i<v.size();i++) is>>v[i];
	return is;
}
 
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        is>>v[i];
    }
    return is;
}
//vector cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<T> &v) {
    bool sp=true;
    if(string(typeid(T).name())=="c") sp=false;
    for(size_t i=0;i<v.size();i++){
        if(i and sp) os<<" ";
        os<<v[i];
    }
    return os;
}
//vector<vector> cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        os<<v[i];
        if(i+1!=v.size()) os<<"\n";
    }
    return os;
}

//Graph out
template<typename T>
inline ostream &operator<<(ostream &os,const Graph &g) {
    for(size_t i=0;i<g.size();i++){
        for(int to:g[i]){
            os<<i<<"->"<<to<<" ";
        }
        os<<endl;
    }
    return os;
}

//WeightGraph out
template<typename T>
inline ostream &operator<<(ostream &os,const WeightGraph<T> &g) {
    for(size_t i=0;i<g.size();i++){
        for(auto e:g[i]){
            os<<i<<"->"<<e.to<<"("<<e.cost<<") ";
        }
        os<<endl;
    }
    return os;
}


//要素数n 初期値x
template<typename T>
inline vector<T> vmake(size_t n,T x){
	return vector<T>(n,x);
}

//a,b,c,x data[a][b][c] 初期値x
template<typename... Args>
auto vmake(size_t n,Args... args){
	auto v=vmake(args...);
	return vector<decltype(v)>(n,move(v));
}
template<typename V,typename T>
void fill(V &v,const T value){
    v=value;
}

template<typename V,typename T>
void fill(vector<V> &vec,const T value){
    for(auto &v:vec) fill(v,value);
}

//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
	os<<p.first<<" "<<p.second;
	return os;
}
 
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
	is>>p.first>>p.second;
	return is;
}
 
//ソート
template<typename T>
inline void vsort(vector<T> &v){
    sort(v.begin(),v.end());
}
 
//逆順ソート
template<typename T>
inline void rvsort(vector<T> &v){
	sort(v.rbegin(),v.rend());
}

//1ビットの数を返す
inline int popcount(int x){
	return __builtin_popcount(x);
}
//1ビットの数を返す
inline int popcount(ll x){
	return __builtin_popcountll(x);
}
template<typename T>
inline void Compress(vector<T> &C){
    sort(C.begin(),C.end());
    C.erase(unique(C.begin(),C.end()),C.end());
}
template<typename T>
inline int lower_idx(const vector<T> &C,T value){
    return lower_bound(C.begin(),C.end(),value)-C.begin();
}
template<typename T>
inline int upper_idx(const vector<T> &C,T value){
    return upper_bound(C.begin(),C.end(),value)-C.begin();
}
//時計回りに90度回転
template<typename T>
inline void rotate90(vector<vector<T>> &C){
    vector<vector<T>> D(C[0].size(),vector<T>(C.size()));
    for(int h=0;h<C.size();h++){
        for(int w=0;w<C[h].size();w++){
            D[w][C.size()-1-h]=C[h][w];
        }
    }
    C=D;
}
//補グラフを返す
//i→iのような辺は加えない
Graph ComplementGraph(const Graph &g){
    size_t sz=g.size();
    bool used[sz][sz];
    fill(used[0],used[sz],false);
    for(size_t i=0;i<sz;i++){
        for(int to:g[i]){
            used[i][to]=true;
        }
    }
    Graph ret(sz);
    for(size_t i=0;i<sz;i++){
        for(size_t j=0;j<sz;j++){
            if(used[i][j]) continue;
            if(i==j) continue;
            ret[i].push_back(j);
        }
    }
    return ret;
}
//グラフの分解 secondはある頂点がどこに対応するか id[i]={2,3}のとき,頂点iはret[2][3]に対応
//無効グラフのみに対応
pair<vector<Graph>,vector<pair<int,int>>> GraphDecomposition(const Graph &g){
    vector<pair<int,int>> id(g.size(),pair<int,int>(-1,-1));
    vector<Graph> ret;
    vector<int> now;
    for(size_t i=0;i<g.size();i++){
        if(id[i].first!=-1) continue;
        id[i].first=ret.size();
        id[i].second=0;
        now.push_back(i);
        for(size_t j=0;j<now.size();j++){
            for(int to:g[now[j]]){
                if(id[to].first==-1){
                    id[to].first=ret.size();
                    id[to].second=now.size();
                    now.push_back(to);
                }
            }
        }
        Graph r(now.size());
        for(size_t j=0;j<now.size();j++){
            r[j]=g[now[j]];
            for(int &to:r[j]){
                to=id[to].second;
            }
        }
        ret.push_back(r);
        now.clear();
    }
    return make_pair(ret,id);
}
//0indexを想定
bool OutGrid(ll h,ll w,ll H,ll W){
    return (h>=H or w>=W or h<0 or w<0);
}

void NO(){
    cout<<"NO"<<"\n";
}
void YES(){
    cout<<"YES"<<"\n";
}
void No(){
    cout<<"No"<<"\n";
}
void Yes(){
    cout<<"Yes"<<"\n";
}
namespace overflow{
    template<typename T>
    T max(){
        return numeric_limits<T>::max();
    }
    template<typename T>
    T ADD(T a,T b){
        T res;
        return __builtin_add_overflow(a,b,&res)?max<T>():res;
    }
    template<typename T>
    T MUL(T a,T b){
        T res;
        return __builtin_mul_overflow(a,b,&res)?max<T>():res;
    }
};
using namespace overflow;
struct mint{
    using u64=uint_fast64_t;
    u64 a;
    constexpr mint() :a(0){}
    constexpr mint(ll x) :a((x>=0)?(x%MOD):(x%MOD+MOD) ) {}

    inline constexpr mint operator+(const mint rhs)const noexcept{
        return mint(*this)+=rhs;
    }
    inline constexpr mint operator-(const mint rhs)const noexcept{
        return mint(*this)-=rhs;
    }
    inline constexpr mint operator*(const mint rhs)const noexcept{
        return mint(*this)*=rhs;
    }
    inline constexpr mint operator/(const mint rhs)const noexcept{
        return mint(*this)/=rhs;
    }
    inline constexpr mint operator+(const ll rhs) const noexcept{
        return mint(*this)+=mint(rhs);
    }
    inline constexpr mint operator-(const ll rhs)const noexcept{
        return mint(*this)-=mint(rhs);
    }
    inline constexpr mint operator*(const ll rhs)const noexcept{
        return mint(*this)*=mint(rhs);
    }
    inline constexpr mint operator/(const ll rhs)const noexcept{
        return mint(*this)/=mint(rhs);
    }

    inline constexpr mint &operator+=(const mint rhs)noexcept{
        a+=rhs.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    inline constexpr mint &operator-=(const mint rhs)noexcept{
        if(rhs.a>a) a+=MOD;
        a-=rhs.a;
        return *this;
    }
    inline constexpr mint &operator*=(const mint rhs)noexcept{
        a=(a*rhs.a)%MOD;
        return *this;
    }
    inline constexpr mint &operator/=(mint rhs)noexcept{
        a=(a*rhs.inverse().a)%MOD;
        return *this;
    }
    inline constexpr mint &operator+=(const ll rhs)noexcept{
        return *this+=mint(rhs);
    }
    inline constexpr mint &operator-=(const ll rhs)noexcept{
        return *this-=mint(rhs);
    }
    inline constexpr mint &operator*=(const ll rhs)noexcept{
        return *this*=mint(rhs);
    }
    inline constexpr mint &operator/=(const ll rhs)noexcept{
        return *this/=mint(rhs);
    }

    inline constexpr mint operator=(const ll x)noexcept{
        a=(x>=0)?(x%MOD):(x%MOD+MOD);
        return *this;
    }

    inline constexpr bool operator==(const mint p)const noexcept{
        return a==p.a;
    }

    inline constexpr bool operator!=(const mint p)const noexcept{
        return a!=p.a;
    }

    inline constexpr mint pow(ll N) const noexcept{
        mint ans(1LL),p(a);
        while(N>0){
            if(bitUP(N,0)){
                ans*=p;
            }
            p*=p;
            N>>=1;
        }
        return ans;
    }
    inline constexpr mint inverse() const noexcept{
        return pow(MOD-2);
    }

};
inline constexpr mint operator+(const ll &a,const mint &b)noexcept{
    return mint(a)+=b;
}
inline constexpr mint operator-(const ll &a,const mint &b)noexcept{
    return mint(a)-=b;
}
inline constexpr mint operator*(const ll &a,const mint &b)noexcept{
    return mint(a)*=b;
}
inline constexpr mint operator/(const ll &a,const mint &b)noexcept{
    return mint(a)/=b;
}
//cout
inline ostream &operator<<(ostream &os,const mint &p) {
    return os<<p.a;
}

//cin
inline istream &operator>>(istream &is,mint &p) {
    ll t;
    is>>t;
    p=t;
    return is;
}

struct Binominal{
    vector<mint> fac,finv,inv; //fac[n]:n! finv:(n!)の逆元
    int sz;
    Binominal(int n=10) :sz(1){
        if(n<=0) n=10;
        init(n);
    }
    inline void init(int n){
        fac.resize(n+1,1);
        finv.resize(n+1,1);
        inv.resize(n+1,1);
        for(int i=sz+1;i<=n;i++){
            fac[i]=fac[i-1]*i;
            inv[i]=MOD-inv[MOD%i]*(MOD/i);
            finv[i]=finv[i-1]*inv[i];
        }
        sz=n;
    }
    //nCk(n,k<=N) をO(1)で求める
    inline mint com(int n,int k){
        if(n<k) return mint(0);
        if(n<0 || k<0) return mint(0);
        if(n>sz) init(n);
        return fac[n]*finv[k]*finv[n-k];
    }
    //nCk(k<=N) をO(k)　で求める 
    inline mint rcom(ll n,int k){
        if(n<0 || k<0 || n<k) return mint(0);
        if(k>sz) init(k);
        mint ret(1);
        for(int i=0;i<k;i++){
            ret*=n-i;
        }
        ret*=finv[k];
        return ret;
    }

    //重複組み合わせ n種類のものから重複を許してk個を選ぶ
    //〇がn個,|がk個
    inline mint h(int n,int k){
        return com(n+k-1,k);
    }
    //順列の公式
    inline mint P(int n,int k){
        if(n<k) return 0;
        if(n>sz) init(n);
        return fac[n]*finv[n-k];
    }

};
vector<int> Subset(int S,bool zero=false,bool full=false){
    vector<int> ret;
    int now=(S-1)&S;
    if(full and S){
        ret.push_back(S);
    }
    do{
        ret.push_back(now);
        now=(now-1)&S;
    }while(now!=0);
    if(zero){
        ret.push_back(0);
    }
    return ret;
}
template<typename T>
T SUM(const vector<T> &v,int s,int t){
    chmax(s,0);
    chmin(t,int(v.size())-1);
    if(s>t) return 0;
    if(s==0) return v[t];
    else return v[t]-v[s-1];
}
template<typename T>
void buildSUM(vector<T> &v){
    for(size_t i=1;i<v.size();i++){
        v[i]+=v[i-1];
    }
    return;
}

//erase_vertexの頂点を消して
//インデックスを調整したグラフを返す
Graph EraseVertex(Graph graph,vector<int> erase_vertex){
    vector<bool> erase(graph.size(),false);
    vector<int> sum(graph.size(),0);
    int cnt_erase=0;
    for(int idx:erase_vertex){
        if(erase[idx]) continue;
        cnt_erase++;
        erase[idx]=true;
        sum[idx]++;
    }
    for(int i=1;i<(int)sum.size();i++){
        sum[i]+=sum[i-1];
    }
    for(int i=0;i<int(graph.size())-cnt_erase;i++){
        int pre_i=i+sum[i];
        graph[i].clear();
        for(int to:graph[pre_i]){
            if(erase[to]) continue;
            graph[i].push_back(to-sum[to]);
        }
    }
    return graph;
}
//https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
//https://yamakuramun.info/2021/02/24/309/
template<typename T>
vector<pair<T,vector<int>>> YenAlgorithm(const WeightGraph<T> &graph,int k,int s,int t){
    assert(k>=1);
    int N=graph.size();
    const auto max_inf = numeric_limits< T >::max();
    const auto min_inf = numeric_limits< T >::lowest();

    assert(0<=s and s<N);
    assert(0<=t and t<N);
    using P=pair<T,vector<int>>;

    map<vector<int>,unordered_set<int>> ban_edge;
    //Pを返す
    auto dijkstra=[&](const vector<int> &spur_path){
        using pti=pair<T,int>;
        vector<pti> dist(N,pti(max_inf,-1));
        for(int v:spur_path){
            dist[v].first=min_inf;
        }
        priority_queue<pti,vector<pti>,greater<pti>> que;
        int start=s;
        if(spur_path.size()) start=spur_path.back();
        dist[start].first=0;
        auto &ban=ban_edge[spur_path];

        que.emplace(0,start);
        while(!que.empty()){
            T cost;
            int v;
            tie(cost,v)=que.top();
            if(v==t) break;
            que.pop();
            if(dist[v].first<cost) continue;
            for(auto &e:graph[v]){
                if(v==start and ban.count(e.to)) continue;
                auto next_cost=cost+e.cost;
                if(chmin(dist[e.to].first,next_cost)){
                    dist[e.to].second=v;
                    que.emplace(dist[e.to].first,e.to);
                }
            }
        }
        vector<int> path;
        if(dist[t].first==max_inf){
            return P(dist[t].first,path);
        }
        int now=t;
        while(now!=start){
            path.push_back(now);
            now=dist[now].second;
        }
        //reverse(path.begin(),path.end());
        return P(dist[t].first,path);    
    };
    vector<P> ans;
    auto compare=[](P a,P b){
        return a.first>b.first;
    };
    priority_queue<P,vector<P>,decltype(compare)> candidate(compare);
    vector<int> prev_path;
    vector<int> spur_path;
    set<vector<int>> set_ans;
    while(k--){
        if(ans.size()==0){
            auto c=dijkstra(spur_path);
            c.second.push_back(s);
            reverse(c.second.begin(),c.second.end());
            if(c.first!=max_inf) candidate.push(c);
        }else{
            T prev_cost=0;
            for(int i=0;i<int(prev_path.size())-1;i++){
                spur_path.push_back(prev_path[i]);
                ban_edge[spur_path].insert(prev_path[i+1]);
                auto c=dijkstra(spur_path);
                for(int j=i;j>=0;j--) c.second.push_back(prev_path[j]);
                reverse(c.second.begin(),c.second.end());
                c.first+=prev_cost;
                if(c.first!=max_inf) candidate.push(c);
                for(auto &e:graph[prev_path[i]]){
                    if(e.to==prev_path[i+1]) prev_cost+=e.cost;
                }
            }
        }
        bool ok=false;
        while(candidate.size()){
            auto c=candidate.top();
            candidate.pop();
            if(set_ans.count(c.second)) continue;
            ans.push_back(c);
            prev_path=c.second;
            ok=true;
            set_ans.insert(c.second);
            break;
        }
        if(not ok) break;
        spur_path.clear();
    }
    return ans;
}


void solve(){
    int N,M,K;
    cin>>N>>M>>K;
    int s,t;
    cin>>s>>t;
    s--; t--;
    WeightGraph<double> graph(N);
    vector<int> p(N),q(N);
    for(int i=0;i<N;i++){
        cin>>p[i]>>q[i];
    }
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        a--; b--;
        double dp=p[a]-p[b],dq=q[a]-q[b];
        double cost=sqrt(dp*dp+dq*dq);
        graph[a].emplace_back(b,cost);
        graph[b].emplace_back(a,cost);
    }
    auto ans=YenAlgorithm(graph,K,s,t);
    for(int i=0;i<K;i++){
        if(i>=int(ans.size())){
            cout<<-1<<endl;
        }else{
            cout<<ans[i].first<<endl;
        }
    }
}

int main(){
    bin101();
    int T=1;
    //cin>>T;
    while(T--) solve();
}

yukicoder

結果

テストケース

ソースコード