제출 #383654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383654		davooddkareshki	꿈 (IOI13_dreaming)	C++17	54 / 100	81 ms	14316 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const int inf = 1e9;
const int maxn = 1e5+10;
const int mod = 1e9+7;

vector<pii> g[maxn];
bool mark[maxn];
vector<int> fel;
int par[maxn], h[maxn], V;

void dfs(int v)
{
    if(h[v] > h[V]) V = v;

    mark[v] = 1;
    for(auto e : g[v])
    {
        int u = e.F, w = e.S;
        if(u != par[v])
        {
            par[u] = v;
            h[u] = h[v] + w;
            dfs(u);
        }
    }
}

/*int A[8] = {0, 8, 2, 5, 5, 1, 1, 10};
int B[8] = {8, 2, 7, 11, 1, 3, 9, 6};
int T[8] = {4, 2, 4, 3, 7, 1, 5, 3};*/
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for(int i = 0; i < M; i++)
    {
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }

    int ANS = 0;
    for(int v = 0; v < N; v++)
        if(!mark[v])
        {
            V = v;
            dfs(v);

            int X = V;
            V = X;
            h[X] = 0; par[X] = 0;
            dfs(X);

            int Y = V;
            int ans = h[Y];
            while(V != X)
            {
                ans = min(ans, max(h[Y]-h[V],h[V]));
                V = par[V];
            }
            fel.push_back(ans);
            ANS = max(ANS,h[Y]);
        }

    sort(fel.begin(), fel.end());
    if((int)fel.size() == 1) return ANS;
    if((int)fel.size() == 2) return max(fel[0] + fel[1] + L, ANS);

    //cout<< ANS <<" ";
    int MM = (int)fel.size();
    return max({fel[MM-1] + fel[MM-2] + L, fel[MM-2] + fel[MM-3] + 2 * L, ANS});
}
/*
signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout<< travelTime(12, 8, 2);
}*/

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