#646569 (C++17) No.1473 おでぶなおばけさん

提出ソース

結果

問題	No.1473 おでぶなおばけさん
ユーザー	bayashiko
提出日時	2021-04-09 22:58:48
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	125 ms / 2,000 ms
コード長	8,806 bytes
コンパイル時間	6,133 ms
コンパイル使用メモリ	312,752 KB
実行使用メモリ	21,576 KB
最終ジャッジ日時	2024-06-25 06:43:51
合計ジャッジ時間	10,553 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	116 ms 19,776 KB
testcase_03	AC	86 ms 14,792 KB
testcase_04	AC	62 ms 12,848 KB
testcase_05	AC	23 ms 6,124 KB
testcase_06	AC	95 ms 14,772 KB
testcase_07	AC	125 ms 21,452 KB
testcase_08	AC	125 ms 21,452 KB
testcase_09	AC	121 ms 21,576 KB
testcase_10	AC	32 ms 5,376 KB
testcase_11	AC	32 ms 5,376 KB
testcase_12	AC	32 ms 5,376 KB
testcase_13	AC	21 ms 5,376 KB
testcase_14	AC	15 ms 5,376 KB
testcase_15	AC	28 ms 5,376 KB
testcase_16	AC	31 ms 5,376 KB
testcase_17	AC	4 ms 5,376 KB
testcase_18	AC	6 ms 5,376 KB
testcase_19	AC	32 ms 6,564 KB
testcase_20	AC	56 ms 13,412 KB
testcase_21	AC	59 ms 10,888 KB
testcase_22	AC	62 ms 19,652 KB
testcase_23	AC	50 ms 17,592 KB
testcase_24	AC	50 ms 17,000 KB
testcase_25	AC	63 ms 19,232 KB
testcase_26	AC	69 ms 19,968 KB
testcase_27	AC	26 ms 10,056 KB
testcase_28	AC	94 ms 20,852 KB
testcase_29	AC	56 ms 9,568 KB
testcase_30	AC	74 ms 10,584 KB
testcase_31	AC	94 ms 21,184 KB
testcase_32	AC	64 ms 14,556 KB
testcase_33	AC	58 ms 13,712 KB
testcase_34	AC	37 ms 10,292 KB
testcase_35	AC	30 ms 7,552 KB
testcase_36	AC	67 ms 16,448 KB
testcase_37	AC	72 ms 17,180 KB
testcase_38	AC	16 ms 6,416 KB
testcase_39	AC	32 ms 5,376 KB
testcase_40	AC	31 ms 5,376 KB
testcase_41	AC	28 ms 5,376 KB
testcase_42	AC	29 ms 5,376 KB
testcase_43	AC	50 ms 13,216 KB
testcase_44	AC	51 ms 13,216 KB
testcase_45	AC	51 ms 13,220 KB
testcase_46	AC	101 ms 17,132 KB
testcase_47	AC	124 ms 19,140 KB
testcase_48	AC	106 ms 17,492 KB

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

ソースコード

raw source code

#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define flc(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vec vector<lint>
#define nep(x) next_permutation(all(x))
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=3e5+5;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//vector<int> bucket[MAX_N/1000];
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#include<atcoder/all>
using namespace atcoder;
typedef __int128_t llint;

template<class T>
struct edge{
    lint to,num;
    T cost;
};

template<class T>
struct Graph{
    vector<vector<edge<T>>> E;
    vector<T> A;
    vector<T> ES;
    vector<edge<T>> E_num;
    vector<T> ds_prev;
    vector<bool> reach;
    vector<T> dis;
    int esize;
    int dlast;
    bool dis_calced=false;
    Graph(){
        esize=0;
    };
    Graph(size_t n){
        A.resize(n);
        E.resize(n);
        reach.resize(n);
        dis.resize(n);
        esize=0;
    }
    size_t v_size() const{
        return (A.size());
    }
    size_t e_size() const{
        return (E.size());
    }
    void clear(){
        E.clear();
        ES.clear();
        E_num.clear();
        esize=0;
    }
    void all_clear(){
        E.clear();
        ES.clear();
        E_num.clear();
        A.clear();
        esize=0;
    }
    int add_edge(lint from,lint to,T cost=1){
        E[from].push_back({to,esize,cost});
        E_num.push_back({to,esize,cost});
        esize++;
        return esize;
    }
    int add_edge_bi(lint from,lint to,T cost=1){
        E[from].push_back({to,esize,cost});
        E_num.push_back({to,esize,cost});
        esize++;
        E[to].push_back({from,esize,cost});
        E_num.push_back({from,esize,cost});
        esize++;
        return esize;
    }
    vector<T> dijkstra(int begin){
        dlast=begin;
        vector<T> d(A.size());
        ds_prev.resize(A.size());
        rep(i,A.size()) ds_prev[i]=i;
        fill(all(d),LINF);
        priority_queue<pair<T,lint>,vector<pair<T,lint>>,greater<pair<T,lint>>> que;
        d[begin]=0;
        que.push(pair<T,lint>(0,begin));
        while(!que.empty()){
            pair<T,lint> p=que.top();
            que.pop();
            T v=p.second;
            if(d[v]<p.first) continue;
            rep(i,E[v].size()){
                edge<T> e=E[v][i];
                if(d[e.to]>d[v]+e.cost){
                    d[e.to]=d[v]+e.cost;
                    ds_prev[e.to]=v;
                    que.push(pair<T,lint>(d[e.to],e.to));
                }
            }
        }
        return d;
    }
    vector<lint> dk_short_path(int to){
        vector<lint> res;
        res.push_back(to);
        while(ds_prev[to]!=to){
            res.push_back(ds_prev[to]);
            to=ds_prev[to];
        }
        reverse(all(res));
        return res;
    }
    vector<lint> reachable(int begin){
        bool reach[A.size()]={};
        vector<lint> res;
        queue<lint> q;
        q.push(begin);
        reach[begin]=true;
        while(!q.empty()){
            lint now=q.front();
            q.pop();
            res.push_back(now);
            rep(i,E[now].size()) if(!reach[E[now][i].to]){
                reach[E[now][i].to]=true;
                q.push(E[now][i].to);
            }
        }
        return res;
    }
    
    //for unweighted graph
    vector<T> disBFS(int begin){
        ds_prev.resize(A.size());
        rep(i,A.size()) ds_prev[i]=i;
        dlast=begin;
        vector<T> d(A.size());
        bool reach[A.size()]={};
        queue<pair<lint,T>> q;
        q.push({begin,0});
        reach[begin]=true;
        while(!q.empty()){
            pair<lint,T> now=q.front();
            q.pop();
            d[now.fi]=now.se;
            rep(i,E[now.fi].size()) if(!reach[E[now.fi][i].to]){
                reach[E[now.fi][i].to]=true;
                q.push({E[now.fi][i].to,now.se+E[now.fi][i].cost});
                ds_prev[E[now.fi][i].to]=now.fi;
            }
        }
        return d;
    }
    vector<T> disBFS_INF(int begin){
        ds_prev.resize(A.size());
        rep(i,A.size()) ds_prev[i]=i;
        dlast=begin;
        vector<T> d(A.size(),LINF);
        d[begin]=0;
        bool reach[A.size()]={};
        reach[begin]=true;
        queue<pair<T,T>> q;
        q.push({begin,0});
        while(!q.empty()){
            pair<T,T> now=q.front();
            q.pop();
            d[now.fi]=now.se;
            rep(i,E[now.fi].size()) if(!reach[E[now.fi][i].to]){
                reach[E[now.fi][i].to]=true;
                q.push({E[now.fi][i].to,now.se+E[now.fi][i].cost});
                ds_prev[E[now.fi][i].to]=now.fi;
            }
        }
        return d;
    }
    // for tree
    vector<lint> diameter(){ //長さとパス(k個)の計k+1の長さのvectorを返す
        vector<lint> d1=disBFS(0);
        int far1=max_element(all(d1))-d1.begin();
        vector<lint> d2=disBFS(far1);
        int far2=max_element(all(d2))-d2.begin();
        vector<lint> res;
        res.push_back(*max_element(all(d2)));
        vector<lint> path=dk_short_path(far2);
        rep(i,path.size()) res.push_back(path[i]);
        return res;
    }
    bool lca_inited=false;
    lint root=0;
    vector<vector<lint>> parent;
    vector<lint> depth;

    void lcadfs(lint v,lint p,lint d){
        parent[0][v]=p;
        depth[v]=d;
        rep(i,E[v].size()) if(E[v][i].to!=p) lcadfs(E[v][i].to,v,d+1);
    }

    void lcainit(){
        int V=A.size();
        depth.resize(V);
        int log=0;
        while((1<<log)<=V) log++;
        log++;
        parent.resize(log);
        rep(i,log) parent[i].resize(V);
        lcadfs(root,-1,0);
        rep(k,log-1) rep(v,V){
            if(parent[k][v]<0) parent[k+1][v]=-1;
            else parent[k+1][v]=parent[k][parent[k][v]];
        }
    }
    lint lca(lint u,lint v){
        if(!lca_inited){
            lca_inited=true;
            lcainit();
        }
        if(depth[u]>depth[v]) swap(u,v);
        rep(k,parent.size()) if((depth[v]-depth[u])>>k&1) v=parent[k][v];
        if(u==v) return u;
        reprev(k,parent.size()){
            if(parent[k][u]!=parent[k][v]){
                u=parent[k][u];
                v=parent[k][v];
            }
        }
        return parent[0][u];
    }
    vector<lint> tree_path(lint s,lint t){
        lint lc=lca(s,t);
        vector<lint> ps,pt;
        lint now=s;
        while(true){
            if(now==lc) break;
            ps.push_back(now);
            now=parent[0][now];
        }
        now=t;
        while(true){
            pt.push_back(now);
            if(now==lc) break;
            now=parent[0][now];
        }
        reverse(pt.begin(),pt.end());
        ps.insert(ps.end(),pt.begin(),pt.end());
        return ps;
    }
    void make_grid(vector<string> S){
        all_clear();
        int n=S.size()*S[0].length();
        A.resize(n);
        E.resize(n);
        reach.resize(n);
        dis.resize(n);
        esize=0;
        int H=S.size(),W=S[0].length();
        rep(i,H) rep(j,W){
            int now=i*W+j;
            if(S[i][j]=='#') continue;
            if(i>0) if(S[i-1][j]!='#') add_edge(now,now-W);
            if(i<H-1) if(S[i+1][j]!='#') add_edge(now,now+W);
            if(j>0) if(S[i][j-1]!='#') add_edge(now,now-1);
            if(j<W-1) if(S[i][j+1]!='#') add_edge(now,now+1);
        }
    }
    void resize(lint n){
        A.resize(n);
        E.resize(n);
        reach.resize(n);
        dis.resize(n);
    }
};

int main(void){
    int N,M;
    cin >> N >> M;
    int S[M],T[M],D[M];
    rep(i,M) cin >> S[i] >> T[i] >> D[i],S[i]--,T[i]--;
    lint lo=1,hi=2e9;
    while(hi-lo>1){
        dsu uf(N);
        lint mid=(hi+lo)/2;
        rep(i,M) if(D[i]>=mid) uf.merge(S[i],T[i]);
        if(uf.same(0,N-1)) lo=mid;
        else hi=mid;
    }
    Graph<lint> G(N);
    rep(i,M) if(lo<=D[i]) G.add_edge_bi(S[i],T[i]);
    vector<lint> res=G.disBFS(0);
    cout << lo << " " << res[N-1] << endl;
}

yukicoder

結果

テストケース

ソースコード