제출 #575407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575407		ogibogi2004	꿈 (IOI13_dreaming)	C++14	18 / 100	39 ms	12108 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int sz=0;
bool vis[MAXN];
std::vector<std::pair<int,int> > g[MAXN];
int mpd[MAXN];// max path down
void dfs_init(int u,int par)
{
    mpd[u]=0;
    vis[u]=1;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        dfs_init(xd.first,u);
        mpd[u]=max(xd.second+mpd[xd.first],mpd[u]);
    }
}
int dfs_find(int u,int par,int len_up)
{
    int ret=max(mpd[u],len_up);
    int maxd=-1,ch=-1,che=-1;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        if(mpd[xd.first]>maxd)
        {
            maxd=mpd[xd.first];
            ch=xd.first;
            che=xd.second;
        }
    }
    if(ch==-1)
    {
        return ret;
    }
    len_up+=che;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        if(xd.first==ch)continue;
        len_up=max(len_up,mpd[xd.first]+che+xd.second);
    }
    return min(ret,dfs_find(ch,u,len_up));
}
void solve(int u)
{
    dfs_init(u,0);
    sz=dfs_find(u,0,0);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    for(int i=0;i<M;i++)
    {
        A[i]++;
        B[i]++;
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }
    vector<int>comps;
    for(int i=1;i<=N;i++)
    {
        if(vis[i]==0)
        {
            sz=0;
            solve(i);
            comps.push_back(sz);
        }
    }

    sort(comps.rbegin(),comps.rend());
    if(comps.size()==1)return comps[0];
    if(comps.size()==2)return comps[0]+comps[1]+L;
    return max(comps[0]+comps[1]+L,comps[1]+comps[2]+L+L);
}

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