Submission #557396

#	Time	Username	Problem	Language	Result	Execution time	Memory
557396		ljuba	Dreaming (IOI13_dreaming)	C++17	0 / 100	1096 ms	9772 KiB

dreaming

#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) {
        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 = INF;
            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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23