Submission #589709

#	Time	Username	Problem	Language	Result	Execution time	Memory
589709		MadokaMagicaFan	Dreaming (IOI13_dreaming)	C++14	100 / 100	91 ms	19388 KiB

dreaming

#include "bits/stdc++.h"
/* #define ONPC */
#ifndef ONPC
    #include "dreaming.h"
#endif


using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second

using pi = pair<int,int>;

const int N = 1e5;
vector<pi> adj[N];

int bd[N][2];
int ds[N];

queue<int> tmp;

bitset<N> c;

int
dfs1(int x, int p)
{
    int dst;
    c[x] = 1;
    for (auto u : adj[x]) {
        if (u.fst == p) continue;

        dst = u.scn + dfs1(u.fst,x);
        ds[u.fst] = dst;

        bd[x][1] = max(bd[x][1], min(bd[x][0], dst));
        bd[x][0] = max(bd[x][0], dst);
    }

    return bd[x][0];
}

void
dfs2(int x, int p ,int v)
{
    tmp.push(max(bd[x][0], v));
    for (auto u : adj[x]) {
        if (u.fst == p) continue;

        if (ds[u.fst] == bd[x][0])
            dfs2(u.fst, x, u.scn + max(v,bd[x][1]));
        else
            dfs2(u.fst, x, u.scn + max(v,bd[x][0]));
    }
    return;
}


int
travelTime(int n, int m, int l, int a[], int b[], int t[])
{
    /* assert(n == m+2); */
    for (int i = 0; i < m; ++i) {
        adj[a[i]].pb({b[i],t[i]});
        adj[b[i]].pb({a[i],t[i]});
    }

    int cnt = 0;
    int mnv, mxv;

    vector<pi> vals;
    for (int i = 0; i < n; ++i) {
        if (c[i]) continue;
        dfs1(i,i);
        mnv = inf;
        mxv = -inf;

        dfs2(i,i,0);
        while (sz(tmp)) {
            int u = tmp.front();
            tmp.pop();
            mnv = min(mnv,u);
            mxv = max(mxv,u);
        }

        vals.pb({mnv,mxv});

        ++cnt;
    }

    int ans = 0;


    vector<int> mv;
    for (int i = 0; i < sz(vals); ++i) {
        ans = max(ans,vals[i].scn);
        mv.pb(vals[i].fst);
    }

    sort(mv.begin(), mv.end());
    reverse(mv.begin(), mv.end());

    if (cnt > 1)
        ans = max(ans, l + mv[0] + mv[1]);
    if (cnt > 2)
        ans = max(ans, l * 2 + mv[1] + mv[2]);

    return ans;
}

#ifdef ONPC
void
solve()
{
    int n, m , l;

    cin >> n >> m >> l;

    int a[N];
    int b[N];
    int t[N];

    for (int i = 0; i < m; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    for (int i = 0; i < m; ++i) cin >> t[i];

    cout << travelTime(n,m,l, a, b, t) << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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