Submission #1133771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133771		t9unkubj	Dreaming (IOI13_dreaming)	C++20	100 / 100	185 ms	19572 KiB

dreaming

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#include "dreaming.h"
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
/*
コストa,bであるものをマージ>a+b+Lコスト
連結成分のコストはmin(max(a+L,b),max(a,b+L))
小さい方からマージ
*/
int solve(int n,int m,int l,vc<int>a,vc<int>b,vc<int>T){
    vvc<pair<int,int>>g(n);
    rep(i,m){
        g[a[i]].push_back({b[i],T[i]});
        g[b[i]].push_back({a[i],T[i]});
    }
    vc<int>seen(n);
    priority_queue<ll>costs;
    
    ll ans=0;
    rep(i,n){
        if(!seen[i]){
            auto D=[&](int st){
                unordered_map<ll,ll>md;
                auto update=[&](int x,ll d){
                    if(!md.count(x)||md[x]>d){
                        md[x]=d;
                        return 1;
                    }   
                    return 0;
                };
                update(st,0);
                queue<int>que;
                que.push(st);
                while(que.size()){
                    auto p=que.front();que.pop();
                    seen[p]=1;
                    for(auto&[to,w]:g[p]){
                        if(update(to,md[p]+w)){
                            que.push(to);
                        }
                    }
                }
                pair<ll,ll>res{(ll)-2e10,(ll)-2e10};
                for(auto&[x,y]:md){
                    chmax(res,pair<ll,ll>{y,x});
                }
                return res;
            };
            auto a1=D(i).second;
            auto a2=D(a1).second;

            auto MX=[&](int st){
                unordered_map<ll,ll>md;
                auto update=[&](int x,ll d){
                    if(!md.count(x)||md[x]>d){
                        md[x]=d;
                        return 1;
                    }   
                    return 0;
                };
                queue<int>que;
                que.push(st);
                update(st,0);
                while(que.size()){
                    auto p=que.front();que.pop();
                    for(auto&[to,w]:g[p]){
                        if(update(to,md[p]+w)){
                            que.push(to);
                        }
                    }
                }
                return md;
            };
            ll C=2e10;
            auto m1=MX(a1),m2=MX(a2);
            for(auto&[x,y]:m1){
                chmin(C,max(m1[x],m2[x]));
            }
            for(auto&[x,y]:m1)chmax(ans,y);
            for(auto&[x,y]:m2)chmax(ans,y);
            costs.push(C);
        }
    }

    while(costs.size()>=2){
        auto p=costs.top();costs.pop();
        auto q=costs.top();costs.pop();
        chmax(ans,(p+q+l));
        costs.push(min(max(p,q+l),max(p+l,q)));
    }
    return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vc<int>a(M),b(M),t(M);
    rep(i,M)a[i]=A[i],b[i]=B[i],t[i]=T[i];
    return solve(N,M,L,a,b,t);
}
namespace judge{
    void run(){
        int n,m,l;
        cin>>n>>m>>l;
        vc<int>a(m),b(m),t(m);
        rep(i,m)cin>>a[i]>>b[i]>>t[i];
        dbg(solve(n,m,l,a,b,t));
    }
};
//int main(){judge::run();}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23