Submission #1208483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208483		andrejikus	Dreaming (IOI13_dreaming)	C++20	100 / 100	185 ms	34944 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

const int N = 1e5 + 3;
const int inf = 2e9;
ll dp[N], dist[N], last[N];
bool vis[N];
multiset<ll> val[N];
vector<pair<int, ll>> adj[N];
int node = -1, ansnode = inf;

void dfs(int u, int p) {
    vis[u] = true;
    dp[u] = 0;
    for (auto [x, w] : adj[u]) if (x != p) {
        dfs(x, u);
        dp[u] = max(dp[u], dp[x]+w);
        val[u].insert(dp[x]+w);
    }
}

void reroot(int u, int p) {
    if (ansnode > dp[u]) {
        node = u; ansnode = dp[u]; last[u] = dp[u];
    }
    for (auto [x, w] : adj[u]) if (x != p) {
        val[u].erase(val[u].find(dp[x]+w));
        dp[u] = (val[u].empty() ? 0 : *val[u].rbegin());
        val[x].insert(dp[u]+w);
        dp[x] = *val[x].rbegin();
        reroot(x, u);
        val[x].erase(val[x].find(dp[u]+w));
        dp[x] = (val[x].empty() ? 0 : *val[x].rbegin());
        val[u].insert(dp[x]+w);
        dp[u] = *val[u].rbegin();
    }
}

void diam(int u, int p) {
    for (auto [x, w] : adj[u]) if (x != p) {
        dist[x] = dist[u]+w;
        diam(x, u);
    }
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    vector<pair<int, int>> nodes;
    for (int i = 0; i < m; i++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        node = -1; ansnode = inf;
        dfs(i, -1);
        reroot(i, -1);
        nodes.push_back({last[node], node});
        //dbg(node, dp[node], i);
    }
    sort(nodes.begin(), nodes.end(), greater<>());
    for (int i = 1; i < nodes.size(); i++) {
        auto [dpp, v] = nodes[i];
        auto [dp1, u] = nodes[0];
        adj[u].push_back({v, L});
        adj[v].push_back({u, L});
    }
    dist[0] = 0;
    diam(0, -1);
    int mx = *max_element(dist, dist + n), u;
    for (int i = 0; i < n; i++) if (dist[i] == mx) u = i;
    dist[u] = 0;
    diam(u, -1);
    mx = *max_element(dist, dist + n);

    return mx;
}

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