Submission #1038829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038829		inkvizytor	Dreaming (IOI13_dreaming)	C++17	18 / 100	27 ms	11856 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> spoj;
vector<vector<pair<int, int>>> g;
vector<int> maxodl1;
vector<int> maxodl2;
vector<int> sr;
vector<int> srdl;
vector<bool> odw;
vector<bool> odws;

void dfs (int v) {
    for (auto u : g[v]) {
        if (!spoj[u.first]) {
            spoj[u.first] = spoj[v];
            dfs(u.first);
            if (maxodl1[v] < maxodl1[u.first]+u.second) {
                maxodl2[v] = maxodl1[v];
                maxodl1[v] = maxodl1[u.first]+u.second;
            }
            else {
                maxodl2[v] = max(maxodl2[v], maxodl1[u.first]+u.second);
            }
        }
    }
}

int odlg = 0;

void zsr (int v) {
    int x = v;
    while (true) {
        sr[spoj[x]] = x;
        srdl[spoj[x]] = maxodl1[x];
        bool b = 0;
        for (auto u : g[x]) {
            if (odw[u.first]) {
                continue;
            }
            odw[u.first] = 1;
            if (maxodl1[x] == maxodl1[u.first]+u.second && max(maxodl2[x], odlg)+u.second < srdl[spoj[x]]) {
                odlg = max(maxodl2[x], odlg)+u.second;
                srdl[spoj[x]] = max(maxodl1[x], odlg);
                x = u.first;
                b = 1;
                break;
            }
        }
        if (!b) {
            break;
        } 
    }
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N);
    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]});
    }
    spoj.resize(N, 0);
    maxodl1.resize(N, 0);
    maxodl2.resize(N, 0);
    int nspoj = 1;
    for (int i = 0; i < N; i++) {
        if (!spoj[i]) {
            spoj[i] = nspoj;
            nspoj++;
            dfs(i);
        }
    }
    sr.resize(nspoj, 0);
    srdl.resize(nspoj, 0);
    odw.resize(N, 0);
    odws.resize(nspoj, 0);
    for (int i = 0; i < N; i++) {
        if (!odws[spoj[i]]) {
            odlg = 0;
            odw[i] = 1;
            odws[spoj[i]] = 1;
            zsr(i);
        }
    }
    int max1 = 0, max2 = 0, max3 = 0;
    for (int i : srdl) {
        if (i > max1) {
            max3 = max2;
            max2 = max1;
            max1 = i;
        }
        else if (i > max2) {
            max3 = max2;
            max2 = i;
        }
        else {
            max3 = max(max3, i);
        }
    }
    if (M == N-1) {
        return max1;
    }
    else if (M == N-2) {
        return max1+max2+L;
    }
    return max(max1+max2+L,max2+max3+2*L);
}

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