Submission #1251037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251037		cpismylifeOwO	Dreaming (IOI13_dreaming)	C++20	100 / 100	172 ms	39124 KiB

dreaming

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

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

int ni, mi, li;
int Ai[MaxN];
int Bi[MaxN];
int Ti[MaxN];

#ifdef cpismylifeOwO
void Inp()
{
    cin >> ni >> mi >> li;
    for (int x = 0; x < mi; x++)
    {
        cin >> Ai[x] >> Bi[x] >> Ti[x];
    }
}
#endif // cpismylifeOwO

struct Edge
{
    int u, v, w;
};

int n, m, l;
Edge edges[MaxN];
vector<int> graph[MaxN];
int best[MaxN];
int secbest[MaxN];
int bestpos[MaxN];
int F[MaxN];
bool visited[MaxN];
vector<int> cur;

void DFS(int u, int p)
{
    visited[u] = true;
    cur.push_back(u);
    best[u] = 0;
    secbest[u] = -1e9;
    bestpos[u] = 0;
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u, w = edges[x].w;
        if (v != p)
        {
            DFS(v, u);
            if (best[u] < best[v] + w)
            {
                secbest[u] = best[u];
                best[u] = best[v] + w;
                bestpos[u] = v;
            }
            else if (secbest[u] < best[v] + w)
            {
                secbest[u] = best[v] + w;
            }
        }
    }
}

void Reroot(int u, int p, int pre)
{
    F[u] = max(best[u], pre);
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u, w = edges[x].w;
        if (v != p)
        {
            if (bestpos[u] == v)
            {
                Reroot(v, u, max(pre, secbest[u]) + w);
            }
            else
            {
                Reroot(v, u, max(pre, best[u]) + w);
            }
        }
    }
}

priority_queue<pair<int, int>> pq;

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n = N;
    m = M;
    l = L;
    for (int x = 1; x <= m; x++)
    {
        edges[x].u = A[x - 1] + 1;
        edges[x].v = B[x - 1] + 1;
        edges[x].w = T[x - 1];
        graph[edges[x].u].push_back(x);
        graph[edges[x].v].push_back(x);
    }
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x])
        {
            cur.clear();
            DFS(x, -1);
            Reroot(x, -1, 0);
            pair<int, int> mi = make_pair(F[cur[0]], cur[0]);
            for (int x : cur)
            {
                mi = min(mi, make_pair(F[x], x));
            }
            pq.push(mi);
        }
    }
    pair<int, int> cur = pq.top();
    pq.pop();
    while (!pq.empty())
    {
        pair<int, int> now = pq.top();
        pq.pop();
        m++;
        edges[m].u = cur.second;
        edges[m].v = now.second;
        //cout << edges[m].u << " " << edges[m].v << "\n";
        edges[m].w = l;
        graph[edges[m].u].push_back(m);
        graph[edges[m].v].push_back(m);
    }
    DFS(1, -1);
    Reroot(1, -1, 0);
    int res = 0;
    for (int x = 1; x <= n; x++)
    {
        res = max(res, F[x]);
    }
    return res;
}

#ifdef cpismylifeOwO
void Exc()
{
    cout << travelTime(ni, mi, li, Ai, Bi, Ti);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}
#endif // cpismylifeOwO

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