제출 #654849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654849		benjaminkleyn	꿈 (IOI13_dreaming)	C++17	100 / 100	881 ms	19232 KiB

dreaming

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;

struct dsuu
{
    vector<int> par;
    dsuu(int n)
    {
        par.resize(n);
        iota(par.begin(), par.end(), 0);
    }
    int find(int u)
    {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }
    bool same(int u, int v)
    {
        return find(u) == find(v);
    }
    void unite(int u, int v)
    {
        u = find(u), v = find(v);
        par[v] = u;
    }
};

dsuu dsu(100000);
vector<pair<int,int>> g[100000];
int rep[100000];

bool vis[100000];
int par[100000];
int dist[100000];
pair<int,int> dfs(int u)
{
    vis[u] = true;
    pair<int,int> res = {0, u};
    for (auto [v, t] : g[u])
        if (!vis[v])
        {
            par[v] = u;
            dist[v] = dist[u] + t;
            pair<int,int> x = dfs(v);
            x.first += t;
            res = max(res, x);
        }
    return res;
}

int furthest(int u)
{
    memset(vis, false, sizeof(vis));
    par[u] = u;
    dist[u] = 0;
    return dfs(u).second;
}

int center(int u)
{
    int x = furthest(u);
    x = furthest(x);
    int y = furthest(x);

    int distmax = dist[y];
    int res = y;
    while (y != x)
    {
        y = par[y];
        if (abs(dist[y]*2 - distmax) < abs(dist[res]*2 - distmax))
            res = y;
    }
    return res;
}

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]});
        dsu.unite(A[i], B[i]);
    }

    vector<pair<int,int>> centers;
    for (int i = 0; i < N; i++)
        if (dsu.find(i) == i)
        {
            int c = center(i);
            int f = furthest(c);
            centers.push_back({dist[f], c});
        }

    sort(centers.rbegin(), centers.rend());
    
    int res = dist[furthest(furthest(centers[0].second))];
    if (centers.size() >= 2)
        res = max(res, centers[0].first + L + centers[1].first);
    if (centers.size() >= 3)
        res = max(res, centers[1].first + 2 * L + centers[2].first);


    return res;
}

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