Submission #119814

#	Time	Username	Problem	Language	Result	Execution time	Memory
119814		dolphingarlic	Dreaming (IOI13_dreaming)	C++14	18 / 100	1076 ms	10360 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<pair<int, int>> graph[100001];
int dp[100001], component[100001], fin[100001];
bool visited[100001];

void dfs1(int node, int indx, int parent = -1) {
    visited[node] = true;
    component[node] = indx;
    for (auto& i : graph[node]) {
        if (i.first == parent) continue;
        dfs1(i.first, indx, node);
    }
}

void dfs(int super, int node, int cost = 0, int parent = -1) {
    for (auto& i : graph[node]) {
        if (i.first == parent) continue;
        dfs(super, i.first, cost + i.second, node);
        dp[super] = max(dp[super], cost + i.second);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    fill(fin, fin + N, INT_MAX);
    FOR(i, 0, M) {
        graph[A[i]].push_back({B[i], T[i]});
        graph[B[i]].push_back({A[i], T[i]});
    }
    int indx = 0;
    FOR(i, 0, N) {
        if (!visited[i]) dfs1(i, indx++);
    }
    // FOR(i, 0, N) cout << component[i] << ' ';
    // cout << '\n';

    FOR(i, 0, N) dfs(i, i);
    // FOR(i, 0, N) cout << dp[i] << ' ';
    // cout << '\n';
    FOR(i, 0, N) fin[component[i]] = min(fin[component[i]], dp[i]);
    sort(fin, fin + indx, greater<int>());

    // cout << fin[0] << ' ' << fin[1] << ' ' << fin[2] << '\n';
    return max(fin[0], max(fin[0] + fin[1] + (indx > 1) * L, fin[1] + fin[2] + 2 * (indx > 2) * L));
}

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