Submission #289074

#	Time	Username	Problem	Language	Result	Execution time	Memory
289074		Atill83	Dreaming (IOI13_dreaming)	C++14	100 / 100	173 ms	34800 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = (int) 3e5 + 5;
ll mes[MAXN], der[MAXN], asa[MAXN];
vector<pii> adj[MAXN];
vector<int> comps;
bool done[MAXN];
ll mn = 0;
void dfs1(int v, int par){
    for(pii u: adj[v]){
        if(u.ff != par){
            der[u.ff] = der[v] + u.ss; 
            dfs1(u.ff, v);
            asa[v] = max(asa[v], asa[u.ff] + u.ss);
        }
    }
}

int dfs(int v, int par, ll upD){
    done[v] = 1;
    mes[v] = max(upD, asa[v]);
    int mx = v;
    multiset<int> st;
    st.insert(upD);
    for(pii u: adj[v]){
        if(u.ff != par){
            st.insert(asa[u.ff] + u.ss);
        }
    }
    if(st.size() == 1){
        mn = max(mn,(ll) *st.rbegin());
    }else if(st.size() > 1){
        mn = max(mn, (ll)(*st.rbegin()) + (*next(st.rbegin())));
    }



    for(pii u: adj[v]){
        if(u.ff != par){
            st.erase(st.lower_bound(asa[u.ff] + u.ss));
            int dg = dfs(u.ff, v, (*st.rbegin()) + u.ss);
            st.insert(asa[u.ff] + u.ss);
            if(mes[dg] < mes[mx]) mx = dg;
        }
    }
    return mx;
}





int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    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]});
    }

    for(int i = 0; i < N; i++){
        if(!done[i]){
            dfs1(i, -1);
            comps.push_back(dfs(i, -1, 0));
        }
        //cerr<<i<<": "<<mes[i]<<endl;
    }

    sort(comps.begin(), comps.end(), [](int a, int b){
        return mes[a] > mes[b];
    });

    if(comps.size() == 1){
        return max(mn, mes[comps[0]]);
    }else if(comps.size() == 2){
        return max(mn, L + mes[comps[0]] + mes[comps[1]]);
    }else{
        return max(mn,max(2*L + mes[comps[1]] + mes[comps[2]], L + mes[comps[0]] + mes[comps[1]]));
    }
}

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