oj.uz

Submission #557397

# Submission time Handle Problem Language Result Execution time Memory
557397 2022-05-05T09:11:04 Z ljuba Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 9804 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);
            }
            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;
      |             ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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