oj.uz

답안 #371007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371007 2021-02-25T14:14:48 Z Fysty 꿈 (IOI13_dreaming) C++17
0 / 100
 84 ms 20336 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
const ll INF=2e18;
vector<pll> ed[100005];
ll dist[100005],n,m,maxx=0;
vector<ll> tmp,path;
void dfs(ll u,ll p)
{
    tmp.pb(u);
    for(auto v:ed[u])
    {
        if(v.F==p) continue;
        dist[v.F]+=dist[u]+v.S;
        dfs(v.F,u);
    }
}
ll findpath(ll u,ll p,ll x)
{
    ll ret=-1;
    if(u==x) ret=dist[x];
    for(auto v:ed[u])
    {
        if(v.F==p) continue;
        ll k=findpath(v.F,u,x);
        if(k!=-1) ret=dist[u];
    }
    path.pb(ret);
    return ret;
}
ll findmid(ll st)
{
    tmp.clear();
    path.clear();
    dfs(st,-1);
    ll mx=0,s=-1;
    for(ll u:tmp)
    {
        if(mx<dist[u]) mx=dist[u],s=u;
        dist[u]=0;
    }
    dfs(s,-1);
    mx=0;
    ll t=-1;
    for(ll u:tmp) if(mx<dist[u]) mx=dist[u],t=u;
    maxx=max(maxx,mx);
    findpath(s,-1,t);
    ll mn=INF;
    for(ll u:path) mn=min(mn,max(mx-u,u));
    return mn;
}
int travelTime(int N,int M,int L,int A[], int B[], int T[])
{
    n=N,m=M;
    vector<ll> ans;
    rep(i,m)
    {
        ll u=A[i],v=B[i],w=T[i];
        ed[u].pb({v,w});
        ed[v].pb({u,w});
    }
    rep(i,n)
    {
        if(dist[i]) continue;
        ans.pb(findmid(i));
    }
    sort(ans.begin(),ans.end(),greater<ll>());
    if(ans.size()==1) return maxx;
    else if(ans.size()==2) return max(maxx,ans[0]+ans[1]+L);
    else return max({maxx,ans[0]+ans[1]+L,ans[1]+ans[2]+2*L});
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 20336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 20336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 7276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 20336 KB Output isn't correct
2 Halted 0 ms 0 KB -