Submission #557398

# Submission time Handle Problem Language Result Execution time Memory
557398 2022-05-05T09:11:41 Z ljuba Dreaming (IOI13_dreaming) C++17
10 / 100
1000 ms 9828 KB
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

int n;
const int mxN = 1e5 + 12;
const int INF = 1e9 + 12;

vector<pair<int, int>> adj[mxN];

bool vis[mxN];

vector<int> koji;

void dfs(int s, int p = -1) {
    vis[s] = true;
    koji.push_back(s);
    for(auto iv : adj[s]) {
        int e = iv.first;
        int w = iv.second;
        if(e == p) continue;
        dfs(e, s);
    }
}

int dist[mxN];

int najdalji(int s) {
    vector<bool> posetili(n, false);
    for(int i = 0; i < n; ++i) dist[i] = -INF;
    queue<int> q;
    q.push(s);
    dist[s] = 0;

    while(!q.empty()) {
        auto tren = q.front();
        posetili[tren] = true;
        q.pop();

        for(auto iv : adj[tren]) {
            int e = iv.first;
            int w = iv.second;
            if(!posetili[e]) {
                q.push(e);
                dist[e] = dist[tren] + w;
            }
        }
    }

    int odg = 0;

    for(int i = 0; i < n; ++i) {
        if(!posetili[i]) continue;
        odg = max(odg, dist[i]);
    }

    return odg;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    for(int i = 0; i < M; ++i) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }

    int ans = 0;

    vector<int> zaSortiranje;

    for(int i = 0; i < n; ++i) {
        if(!vis[i]) {
            koji.clear();
            dfs(i);
            int gas = 0;
            int gas2 = INT_MAX;
            for(auto z : koji) {
                int izraz = najdalji(z);
                gas = max(gas, izraz);
                gas2 = min(gas2, izraz);
            }
            ans = max(ans, gas);
            zaSortiranje.push_back(gas2);
        }
    }

    sort(zaSortiranje.rbegin(), zaSortiranje.rend());

    if(zaSortiranje.size() > 1) {
        ans = max(ans, zaSortiranje[0] + zaSortiranje[1] + L);
    }

    return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:21:13: warning: unused variable 'w' [-Wunused-variable]
   21 |         int w = iv.second;
      |             ^
# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 9828 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 1 ms 2644 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 2 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 9828 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 5464 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 1 ms 2644 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 2 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 4 ms 2644 KB Output is correct
27 Correct 9 ms 2764 KB Output is correct
28 Correct 16 ms 2772 KB Output is correct
29 Correct 4 ms 2644 KB Output is correct
30 Correct 9 ms 2772 KB Output is correct
31 Correct 18 ms 2824 KB Output is correct
32 Incorrect 4 ms 2644 KB Output isn't correct
33 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 9828 KB Time limit exceeded
2 Halted 0 ms 0 KB -