Submission #99220

#	Time	Username	Problem	Language	Result	Execution time	Memory
99220		eriksuenderhauf	Dreaming (IOI13_dreaming)	C++11	100 / 100	119 ms	20572 KiB

dreaming

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "dreaming.h"
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
vii adj[MAXN];
int vis[MAXN], arr[MAXN];
int sz[MAXN], dp2[MAXN];
pair<pii,pii> dp[MAXN];
int ans = 0;

int dfs(int u, int p, int d, int comp) {
    arr[u] = comp;
    vis[u] = 1;
    int mx = 0, mx2 = 0;
    int ind = -1;
    for (pii nx: adj[u]) {
        if (nx.fi == p)
            continue;
        int v = nx.fi;
        int tmp = dfs(v, u, d + nx.se, comp) + nx.se;
        if (mx < tmp) {
            mx2 = mx;
            mx = tmp;
            dp[u] = {{mx, v}, {mx2, ind}};
            ind = v;
        } else if (mx2 < tmp) {
            mx2 = tmp;
            dp[u].se = {mx2, v};
        }
    }
    ans = max(ans, mx + mx2);
    return mx;
}

void dfs2(int u, int p, int w) {
    if (p != -1) {
        if (dp[p].fi.se == u)
            dp2[u] = max(w + dp2[p], w + dp[p].se.fi);
        else
            dp2[u] = max(w + dp2[p], w + dp[p].fi.fi);
    }
    for (pii v: adj[u])
        if (v.fi != p)
            dfs2(v.fi, u, v.se);
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    /*int n, m, l;
    scanf("%d %d %d", &n, &m, &l);*/
    for (int i = 0; i < m; i++) {
        /*int a, b, t;
        scanf("%d %d %d", &a, &b, &t);*/
        adj[a[i]].pb({b[i], t[i]});
        adj[b[i]].pb({a[i], t[i]});
    }
    int comp = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i])
            continue;
        dfs(i, -1, 0, comp);
        dfs2(i, -1, 0);
        sz[comp] = INF;
        comp++;
    }
    for (int i = 0; i < n; i++)
        sz[arr[i]] = min(sz[arr[i]], max(dp2[i], dp[i].fi.fi));
    sort(sz, sz + comp);
    if (comp > 1)
        ans = max(ans, sz[comp - 1] + l + sz[comp - 2]);
    if (comp > 2)
        ans = max(ans, sz[comp - 2] + 2 * l + sz[comp - 3]);
    //pri(ans);
    return ans;
}

/*int main()
{

    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