結果

問題 No.1473 おでぶなおばけさん
ユーザー bayashikobayashiko
提出日時 2021-04-09 22:58:48
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 8,806 bytes
コンパイル時間 6,565 ms
コンパイル使用メモリ 310,132 KB
実行使用メモリ 21,508 KB
最終ジャッジ日時 2023-09-07 12:39:29
合計ジャッジ時間 11,230 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 129 ms
21,276 KB
testcase_03 AC 87 ms
14,704 KB
testcase_04 AC 64 ms
12,556 KB
testcase_05 AC 23 ms
6,236 KB
testcase_06 AC 99 ms
14,624 KB
testcase_07 AC 137 ms
21,256 KB
testcase_08 AC 130 ms
21,508 KB
testcase_09 AC 128 ms
21,360 KB
testcase_10 AC 32 ms
4,956 KB
testcase_11 AC 33 ms
4,724 KB
testcase_12 AC 33 ms
4,724 KB
testcase_13 AC 21 ms
4,380 KB
testcase_14 AC 15 ms
4,376 KB
testcase_15 AC 28 ms
4,540 KB
testcase_16 AC 31 ms
4,680 KB
testcase_17 AC 4 ms
4,376 KB
testcase_18 AC 5 ms
4,376 KB
testcase_19 AC 32 ms
6,424 KB
testcase_20 AC 56 ms
13,564 KB
testcase_21 AC 60 ms
10,848 KB
testcase_22 AC 67 ms
19,340 KB
testcase_23 AC 54 ms
18,168 KB
testcase_24 AC 56 ms
17,820 KB
testcase_25 AC 77 ms
19,432 KB
testcase_26 AC 77 ms
20,944 KB
testcase_27 AC 27 ms
9,908 KB
testcase_28 AC 103 ms
21,348 KB
testcase_29 AC 57 ms
9,404 KB
testcase_30 AC 75 ms
10,188 KB
testcase_31 AC 102 ms
20,844 KB
testcase_32 AC 66 ms
14,280 KB
testcase_33 AC 60 ms
13,580 KB
testcase_34 AC 37 ms
10,256 KB
testcase_35 AC 30 ms
7,220 KB
testcase_36 AC 68 ms
16,920 KB
testcase_37 AC 74 ms
18,932 KB
testcase_38 AC 16 ms
6,248 KB
testcase_39 AC 32 ms
4,712 KB
testcase_40 AC 31 ms
4,740 KB
testcase_41 AC 30 ms
4,676 KB
testcase_42 AC 30 ms
4,720 KB
testcase_43 AC 51 ms
12,972 KB
testcase_44 AC 51 ms
12,976 KB
testcase_45 AC 52 ms
12,988 KB
testcase_46 AC 109 ms
17,692 KB
testcase_47 AC 132 ms
19,312 KB
testcase_48 AC 111 ms
18,920 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0