Submission #572126

#	Time	Username	Problem	Language	Result	Execution time	Memory
572126		stevancv	Dreaming (IOI13_dreaming)	C++14	100 / 100	83 ms	17700 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
int mod = 1000000007;
vector<array<int, 2>> g[N];
bool was[N];
int up[N], down[N];
vector<int> v;
void Dfs(int s) {
    was[s] = 1;
    v.push_back(s);
    for (auto u : g[s]) {
        if (was[u[0]] == 0) {
            Dfs(u[0]);
            smax(down[s], down[u[0]] + u[1]);
        }
    }
}
void Dfs1(int s, int di) {
    was[s] = 1;
    up[s] = di;
    int mx1, mx2;
    mx1 = mx2 = 0;
    for (auto u : g[s]) {
        if (was[u[0]] == 0) {
            if (down[u[0]] + u[1] > mx1) {
                mx2 = mx1;
                mx1 = down[u[0]] + u[1];
            }
            else smax(mx2, down[u[0]] + u[1]);
        }
    }
    for (auto u : g[s]) {
        if (was[u[0]] == 0) {
            if (down[u[0]] + u[1] == mx1) Dfs1(u[0], max(di, mx2) + u[1]);
            else Dfs1(u[0], max(di, mx1) + u[1]);
        }
    }
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for (int i = 0; i < m; i++) {
        g[a[i]].push_back({b[i], t[i]});
        g[b[i]].push_back({a[i], t [i]});
    }
    int ans = 0;
    vector<int> svi;
    for (int i = 0; i < n; i++) {
        if (was[i] == 0) {
            Dfs(i);
            for (int j : v) was[j] = 0;
            Dfs1(i, 0);
            int koji = 1e9;
            for (int j : v) {
                int x = max(up[j], down[j]);
                smax(ans, x);
                smin(koji, x);
            }
            v.clear();
            svi.push_back(koji);
        }
    }
    sort(svi.rbegin(), svi.rend());
    if (svi.size() >= 2) smax(ans, svi[0] + svi[1] + l);
    if (svi.size() >= 3) smax(ans, svi[1] + svi[2] + 2 * l);
    return ans;
}

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