Submission #557111

#	Time	Username	Problem	Language	Result	Execution time	Memory
557111		ljuba	Dreaming (IOI13_dreaming)	C++17	10 / 100	1100 ms	14596 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

int n;

const int mxN = 1e5 + 12;
bool vis[mxN];

int dep[mxN];
pair<int, int> iznad[mxN];

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

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

        if(e == p) continue;
        iznad[e] = make_pair(s, w);
        dfs(e, s);
    }
}

int dist[mxN];

vector<int> posetili;

void dfsNajdalji(int s, int p = -1) {
    if(p == -1) {
        dist[s] = 0;
    }

    posetili.push_back(s);

    for(auto iv : adj[s]) {
        int e = iv.first;
        int w = iv.second;

        if(e == p) continue;
        dist[e] = dist[s] + w;
        dfsNajdalji(e, s);
    }
}

int nadjiNajdalji(int s) {
    posetili.clear();
    dfsNajdalji(s);

    pair<int, int> p{-1, -1};
    for(auto i : posetili) {
        pair<int, int> temp{dist[i], i};
        p = max(p, temp);
    }

    return p.second;
}

int mozda(int s) {
    posetili.clear();
    dfsNajdalji(s);

    auto novi = posetili;

    int ans = int(1e9 + 12);

    for(auto z : novi) {
        posetili.clear();
        dfsNajdalji(z);
        int tren = 0;
        for(auto x : posetili) {
            tren = max(tren, dist[x]);
        }
        ans = min(ans, tren);
    }
    return ans;
}

pair<int, int> putanja(int a, int b) {
    int pocA = a;
    int pocB = b;

    // for(int i = 0; i < n; ++i) {
    //     cerr << i << " " << dep[i] << endl;
    // }

    if(dep[a] < dep[b]) swap(a, b); //dep[a] >= dep[b]

    int suma = 0;
    while(dep[a] > dep[b]) {
        // cerr << a << " " << b << endl;
        suma += iznad[a].second;
        a = iznad[a].first;
    }

    while(a != b) {
        suma += iznad[a].second;
        suma += iznad[b].second;
        a = iznad[a].first;
        b = iznad[b].first;
    }

    int rodjak = a;

    a = pocA;
    b = pocB;
    int odg = int(1e9 + 12);
    int trenutno = 0;

    odg = suma;

    // if(a == rodjak && b == rodjak) {
    //     odg = 0;
    // }

    // cerr << a << " " << rodjak << endl;
    // cerr << b << " " << rodjak << endl;

    while(a != rodjak) {
        odg = min(odg, max(trenutno, suma - trenutno));
        trenutno += iznad[a].second;
        a = iznad[a].first;
    }

    odg = min(odg, max(trenutno, suma - trenutno));

    trenutno = 0;
    while(b != rodjak) {
        odg = min(odg, max(trenutno, suma - trenutno));
        trenutno += iznad[b].second;
        b = iznad[b].first;
    }

    odg = min(odg, max(trenutno, suma - trenutno));

    return make_pair(suma, odg);
}

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

    vector<int> svi;

    int ans = 0;

    for(int i = 0; i < n; ++i) {
        if(!vis[i]) {
            dfs(i);
            int a = nadjiNajdalji(i);
            int b = nadjiNajdalji(a);
            auto odg = putanja(a, b);
            // svi.push_back(odg.second);
            ans = max(ans, odg.first);
            int qwer = mozda(i);
            svi.push_back(qwer);

            // cerr << odg.first << " " << odg.second << endl;
        }
    }

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

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

    return ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 10 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23