oj.uz

Submission #119814

# Submission time Handle Problem Language Result Execution time Memory
119814 2019-06-22T12:33:44 Z dolphingarlic Dreaming (IOI13_dreaming) C++14
18 / 100
 1000 ms 10360 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 10360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 10360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 10360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6244 KB Output is correct
2 Correct 25 ms 6268 KB Output is correct
3 Correct 25 ms 6264 KB Output is correct
4 Correct 25 ms 6272 KB Output is correct
5 Correct 29 ms 6264 KB Output is correct
6 Correct 31 ms 6436 KB Output is correct
7 Correct 27 ms 6392 KB Output is correct
8 Correct 27 ms 6144 KB Output is correct
9 Correct 24 ms 6144 KB Output is correct
10 Correct 27 ms 6268 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 7 ms 3968 KB Output is correct
13 Correct 6 ms 3968 KB Output is correct
14 Correct 6 ms 3968 KB Output is correct
15 Correct 6 ms 3968 KB Output is correct
16 Correct 6 ms 3968 KB Output is correct
17 Correct 6 ms 3840 KB Output is correct
18 Correct 7 ms 3968 KB Output is correct
19 Correct 7 ms 3968 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 4 ms 2816 KB Output is correct
23 Correct 6 ms 3968 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 10360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 10360 KB Time limit exceeded
2 Halted 0 ms 0 KB -