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

提出ソース

結果

問題	No.1473 おでぶなおばけさん
ユーザー	bayashiko
提出日時	2021-04-09 22:58:48
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	CE (最新) AC (最初)
実行時間	-
コード長	8,806 bytes
コンパイル時間	30,081 ms
コンパイル使用メモリ	5,248 KB
最終ジャッジ日時	2025-01-20 15:04:39
ジャッジサーバーID （参考情報）	judge5 / judge4

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

コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ

コンパイルが30秒の制限時間を超えました

ソースコード

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

結果

コンパイルメッセージ

ソースコード