Submission #492577

#	Time	Username	Problem	Language	Result	Execution time	Memory
492577		uHyHn	Dreaming (IOI13_dreaming)	C++14	100 / 100	125 ms	25036 KiB

dreaming

#include<bits/stdc++.h>

//IBOW
#include "dreaming.h"
#define Task "IOI13_dreaming"
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define rep(i, b) for (int i = (1); i <= (b); ++i)
#define REP(i, b) for (int i = (b); i >= (1); --i)
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define eb emplace_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<long long> vll;

const int N = 2e5 + 10;
const int inf = 2e9 + 10;
const ll INF = 2e18 + 10;
const int MOD = 1e9 + 7;

int n, m, l, dp[N][2], dp_down[N], cnt = 0, diameter = 0, a[N], b[N], t[N];
vector<ii> g[N];
bool vis[N];
vector<ii> center_node;

void find_center(int u, int p, ii &get_center)
{
    if (abs(dp[u][0] - max(dp_down[u], dp[u][1])) < get_center.F)
    {
//        cout << u << ' ' << abs(dp[u][0] - max(dp_down[u], dp[u][1])) << '\n';
        get_center = {abs(dp[u][0] - max(dp_down[u], dp[u][1])), u};
    }
    for (ii e : g[u])
    {
        if (e.F == p) continue;
        find_center(e.F, u, get_center);
    }
}
void dfs(int u, int p = -1)
{
//    cout << u << '\n';
    vi v;
    vis[u] = 1;
    dp[u][0] = dp[u][1] = 0;
    for (ii e : g[u])
    {
        if (e.F == p) continue;
        dfs(e.F, u);
        v.pb(dp[e.F][0] + e.S);
    }
    sort(all(v), greater<int>());
    if (sz(v) >= 2) diameter = max(diameter, v[0] + v[1]);
    if (sz(v) >= 1) diameter = max(diameter, v[0]);
    for (int i = 0; i < min(2, sz(v)); ++i) dp[u][i] = v[i];
}
void dfs1(int u, int p = -1)
{
    for (ii e : g[u])
    {
        if (e.F == p) continue;
        dp_down[e.F] = dp_down[u] + e.S;
        if (dp[u][0] == dp[e.F][0] + e.S)
        {
            dp_down[e.F] = max(dp_down[e.F], dp[u][1] + e.S);
        } else
        {
            dp_down[e.F] = max(dp_down[e.F], dp[u][0] + e.S);
        }
        dfs1(e.F, u);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
    memset(vis, 0, sizeof vis);
    memset(dp_down, 0, sizeof dp_down);
    for (int i = 0; i < m; ++i)
    {
        g[a[i]].pb({b[i], t[i]});
        g[b[i]].pb({a[i], t[i]});
    }
    for (int i = 0; i < n; ++i) if (!vis[i])
    {
        diameter = 0;
//        cnt++;
        dfs(i);
        dfs1(i);
        ii get_center = {inf, -1};
        find_center(i, i, get_center);
        center_node.pb({max(dp[get_center.S][0], dp_down[get_center.S]), get_center.S});
    }
    nth_element(center_node.begin(), center_node.end() - 1, center_node.end());
    for (int i = 0; i < sz(center_node) - 1; ++i)
    {
        g[center_node[i].S].pb({center_node.back().S, l});
        g[center_node.back().S].pb({center_node[i].S, l});
    }
    diameter = 0;
    dfs(0);
    return diameter;
}
//int32_t main()
//{
//    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    if (fopen(Task".in", "r"))
//    {
//        freopen(Task".in", "r", stdin);
//        freopen(Task".out", "w", stdout);
//    }
//    cin >> n >> m >> l;
//    rep(i, m) cin >> a[i] >> b[i] >> t[i];
//    cout << travelTime(n, m, l, a, b, t);
//    return 0;
//}

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