oj.uz

Submission #572121

# Submission time Handle Problem Language Result Execution time Memory
572121 2022-06-03T17:07:48 Z stevancv Dreaming (IOI13_dreaming) C++14
32 / 100
 58 ms 13004 KB 
#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]] > 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13004 KB Output is correct
2 Correct 46 ms 12720 KB Output is correct
3 Correct 27 ms 11060 KB Output is correct
4 Correct 7 ms 4232 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 12 ms 4980 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 20 ms 6944 KB Output is correct
9 Correct 30 ms 9204 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 58 ms 10288 KB Output is correct
12 Correct 46 ms 11500 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Incorrect 2 ms 2664 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13004 KB Output is correct
2 Correct 46 ms 12720 KB Output is correct
3 Correct 27 ms 11060 KB Output is correct
4 Correct 7 ms 4232 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 12 ms 4980 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 20 ms 6944 KB Output is correct
9 Correct 30 ms 9204 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 58 ms 10288 KB Output is correct
12 Correct 46 ms 11500 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Incorrect 2 ms 2664 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6564 KB Output is correct
2 Correct 28 ms 6612 KB Output is correct
3 Correct 29 ms 6496 KB Output is correct
4 Correct 27 ms 6548 KB Output is correct
5 Correct 19 ms 6580 KB Output is correct
6 Correct 20 ms 7080 KB Output is correct
7 Correct 20 ms 6748 KB Output is correct
8 Correct 19 ms 6456 KB Output is correct
9 Correct 18 ms 6512 KB Output is correct
10 Correct 25 ms 6728 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 5 ms 4068 KB Output is correct
13 Correct 5 ms 4048 KB Output is correct
14 Correct 6 ms 4048 KB Output is correct
15 Correct 5 ms 4072 KB Output is correct
16 Correct 5 ms 4048 KB Output is correct
17 Correct 5 ms 3792 KB Output is correct
18 Correct 5 ms 4048 KB Output is correct
19 Correct 7 ms 4048 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 6 ms 4048 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Incorrect 2 ms 2664 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13004 KB Output is correct
2 Correct 46 ms 12720 KB Output is correct
3 Correct 27 ms 11060 KB Output is correct
4 Correct 7 ms 4232 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 12 ms 4980 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 20 ms 6944 KB Output is correct
9 Correct 30 ms 9204 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 58 ms 10288 KB Output is correct
12 Correct 46 ms 11500 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Incorrect 2 ms 2664 KB Output isn't correct
18 Halted 0 ms 0 KB -