Submission #239433

#	Time	Username	Problem	Language	Result	Execution time	Memory
239433		dung11112003	Dreaming (IOI13_dreaming)	C++11	100 / 100	173 ms	24076 KiB

dreaming

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

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 10;

vector <pair <int, int>> adj[maxN];
int flag[maxN], dp_up[maxN], dp_down[maxN], diameter[maxN], d[maxN];
vector <int> root;
int cur_res = 0;

void dfs(int u)
{
    flag[u] = 1;
    for (auto &e: adj[u])
    {
        int v = e.fi, w = e.se;
        if (!flag[v])
        {
            dfs(v);
            uax(dp_down[u], dp_down[v] + w);
        }
    }
}

void dfs2(int u, int S)
{
    flag[u] = 1;
    uax(diameter[S], dp_up[u] + dp_down[u]);
    uin(d[S], max(dp_up[u], dp_down[u]));
    vector <pair <int, int>> edges;
    for (auto &e: adj[u])
    {
        if (!flag[e.fi])
        {
            edges.eb(e);
        }
    }
    if (edges.empty())
    {
        //u is leaf
        return;
    }
    //prefixes
    int mx = dp_down[edges[0].fi] + edges[0].se;
    for (int i = 1; i < (int)edges.size(); i++)
    {
        dp_up[edges[i].fi] = mx + edges[i].se;
        uax(mx, dp_down[edges[i].fi] + edges[i].se);
    }
    //suffixes
    mx = dp_down[edges.back().fi] + edges.back().se;
    for (int i = (int)edges.size() - 2; i >= 0; i--)
    {
        uax(dp_up[edges[i].fi], mx + edges[i].se);
        uax(mx, dp_down[edges[i].fi] + edges[i].se);
    }
    for0(i, edges.size())
    {
        uax(dp_up[edges[i].fi], dp_up[u] + edges[i].se);
    }
    mx = 0;
    for (auto &e: adj[u])
    {
        if (!flag[e.fi])
        {
            dfs2(e.fi, S);
            uax(diameter[S], mx + e.se + dp_down[e.fi]);
            uax(mx, e.se + dp_down[e.fi]);
        }
    }
}

int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
    for0(i, m)
    {
        int u = A[i] + 1, v = B[i] + 1, w = T[i];
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    for1(i, n)
    {
        if (!flag[i])
        {
            root.eb(i);
            dfs(i);
        }
    }
    fill(flag + 1, flag + n + 1, 0);
    fill(d + 1, d + n + 1, 1e9);
    for1(i, n)
    {
        if (!flag[i])
        {
            dfs2(i, i);
        }
    }
    int ans = 1e9;
    if ((int)root.size() > 1)
    {
        sort(all(root), [](int x, int y)
        {
            return d[x] < d[y];
        });
        for (int i = 0; i < (int)root.size(); i++)
        {
            int r = root[i], cur = 0;
            //r is root
            if (i == (int)root.size() - 1)
            {
                uax(cur, d[r] + d[root[i - 1]] + L);
            }
            else
            {
                uax(cur, d[r] + d[root.back()] + L);
            }
            if ((int)root.size() >= 3)
            {
                int u, v, cnt = 0;
                for (int j = (int)root.size() - 1; j >= 0; j--)
                {
                    if (j == i)
                    {
                        continue;
                    }
                    if (cnt == 0)
                    {
                        u = root[j];
                    }
                    else if (cnt == 1)
                    {
                        v = root[j];
                    }
                    else
                    {
                        break;
                    }
                    cnt++;
                }
                uax(cur, d[u] + d[v] + L * 2);
            }
            uin(ans, cur);
        }
    }
    else
    {
        ans = 0;
    }
    for (auto &r: root)
    {
        uax(ans, diameter[r]);
    }
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:172:36: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 uax(cur, d[u] + d[v] + L * 2);
                                 ~~~^
dreaming.cpp:172:29: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 uax(cur, d[u] + d[v] + L * 2);
                          ~~~^

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