Submission #402234

#	Time	Username	Problem	Language	Result	Execution time	Memory
402234		Lobo	Dreaming (IOI13_dreaming)	C++17	100 / 100	109 ms	18140 KiB

dreaming

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

const long long INFll = 1e18;
const int INFii = 1e9;
const long long mod = (long long) 1e9 + 7;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back

#define maxn 110000
//LEMBRAR DE MUDAR

ii n, m, l, d1[maxn], d2[maxn], mark[maxn], pai[maxn], ans; 
vector<pair<ii,ii>> g[maxn];
vector<ii> raio;
pair<ii,ii> dia;



void dfs1(ii a, ii ant) {
    for(auto b : g[a]) {
        if(b.fr == ant) continue;

        d1[b.fr] = d1[a] + b.sc;
        dia = max(dia,mp(d1[b.fr],b.fr));
        dfs1(b.fr, a);
    }
}

void dfs2(ii a) {
    mark[a] = 1;
    
    for(auto b : g[a]) {
        if(mark[b.fr]) continue;

        d2[b.fr] = d2[a] + b.sc;
        dia = max(dia,mp(d2[b.fr],b.fr));
        dfs2(b.fr);
        pai[b.fr] = a;
    }

}


int travelTime(int N,int M,int L,int A[],int B[],int T[]) {
    n = N;
    m = M;
    l = L;

    for(ii i = 0; i < m; i++) {
        g[A[i]].pb(mp(B[i],T[i]));
        g[B[i]].pb(mp(A[i],T[i]));
    }

    ans = 0;
    for(ii i = 0; i < n; i++) {
        if(!mark[i]) {
            d1[i] = 0;
            dia = mp(0,i);
            dfs1(i,i);

            ii aux = dia.sc;
            d2[aux] = 0;
            dia = mp(0,aux);
            dfs2(aux);          

            ii rai = INFii;
            ans = max(ans, dia.fr);

            ii a = dia.sc;
            while(true) {
                rai = min(rai, max(dia.fr - d2[a],d2[a]));
                
                if(a == aux) break;

                a = pai[a];
            }
            
            raio.pb(rai);
        }
    }

    sort(raio.begin(),raio.end());

    ii r1 = raio.back();
    raio.pop_back();

    ii r2 = -INFii;
    ii r3 = -INFii;

    if(!raio.empty()) {
        r2 = raio.back() + l;
        raio.pop_back();
    }

    if(!raio.empty()) {
        r3 = raio.back() + l;
    }

    ans = max({ans, r1+r2, r2+r3});

    return ans;
}

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