제출 #850780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850780		aykhn	꿈 (IOI13_dreaming)	C++14	100 / 100	58 ms	15628 KiB

dreaming

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

using namespace std;
typedef long long ll;

#define pb push_back
#define ins insert
#define pii pair<int, int>
#define fi first
#define se second
#define mpr make_pair
#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;

int n, m, l;
vector<pii> adj[MXN];
vector<vector<int>> comp;
int used[MXN];
int dist[2][MXN];
int c = -1;
int mx, node = -1;
int dia1, dia2;

void dfs(int a)
{
    comp[c].pb(a);
    used[a] = 1;
    for (pii v : adj[a])
    {
        if (used[v.fi]) continue;
        dfs(v.fi);
    }
}

void dfs1(int a, int w = 0, int p = -1)
{
    if (w > mx)
    {
        mx = w;
        dia2 = a;
    }
    for (pii v : adj[a])
    {
        if (v.fi == p) continue;
        dfs1(v.fi, w + v.se, a);
    }
}

void dfs2(int a, int id, int w = 0, int p = -1)
{
    dist[id][a] = w;
    for (pii v : adj[a])
    {
        if (v.fi == p) continue;
        dfs2(v.fi, id, w + v.se, a);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    n = N;
    m = M;
    l = L;
    for (int i = 0; i < m; i++)
    {
        adj[A[i]].pb(mpr(B[i], T[i]));
        adj[B[i]].pb(mpr(A[i], T[i]));
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i])
        {
            c++;
            comp.pb(vector<int> (0));
            dfs(i);
        }
    }
    multiset<int> ms;
    int mx1 = -inf;

    for (int i = 0; i <= c; i++)
    {
        mx = -inf;
        dia1 = dia2 = -1;
        dfs1(comp[i][0]);
        mx = -inf;
        dia1 = dia2;
        dfs1(dia1);
        dfs2(dia1, 0);
        dfs2(dia2, 1);
        int center = comp[i][0];
        for (int u : comp[i])
        {
            if (max(dist[0][u], dist[1][u]) < max(dist[0][center], dist[1][center])) center = u;
        }
        ms.ins(max(dist[0][center], dist[1][center]));
        mx1 = max(mx1, mx);
    }

    if (!c) return max(mx1, *ms.begin());
    auto it = ms.end();
    it--;
    it--;
    auto it1 = it;
    it1--;
    if (c == 1) return max(mx1, *ms.rbegin() + *it + l);
    return max({mx1, *ms.rbegin() + *it + l, *it + *it1 + 2*l});
}

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