Submission #650300

#	Time	Username	Problem	Language	Result	Execution time	Memory
650300		ojoConmigo	Dreaming (IOI13_dreaming)	C++17	0 / 100	47 ms	13272 KiB

dreaming

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

vector<vector<pair<int,int>>> g;
vector<bool> vis;
vector<int> fir,sec,ans;

void dfs1(int nodo, int p,vector<int> & comp){
    vis[nodo] = true;
    comp.push_back(nodo);
    for(auto k : g[nodo]){
        int v = k.first;
        int w = k.second;
        if(v == p)continue;
        dfs1(v,nodo,comp);
        if(fir[v] + w > fir[nodo]){
            sec[nodo] = fir[nodo];
            fir[nodo] = fir[v] + w;
        }else if(fir[v] + w > sec[nodo]){
            sec[nodo] = fir[v] + w;
        }
    }
}

void dfs2(int nodo, int p, int top){
    ans[nodo] = max(fir[nodo],top);
    for(auto k : g[nodo]){
        int v = k.first;
        int w = k.second;
        if(v == p)continue;
        if(fir[v] + w == fir[nodo]) dfs2(v,nodo,max(top,sec[nodo]) + w);
        else dfs2(v,nodo,ans[nodo] + w);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N);
    for(int i=0; i<M; i++){
        int x = A[i];
        int y = B[i];
        int w = T[i];
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    vis.assign(N,false);
    fir.assign(N,0);
    sec.assign(N,0);
    ans.resize(N);
    int m1,m2,m3;
    m1 = m2 = m3 = 0;
    for(int i=0; i<N; i++){
        if(vis[i] == false){
            vector<int> comp;
            dfs1(i,-1,comp);
            dfs2(i,-1,0);
            int q = 1e9;
            for(int x : comp){
                q = min(q,ans[x]);
            }
            if(q > m1){
                m3 = m2;
                m2 = m1;
                m1 = q;
            }else if(q > m2){
                m3 = m2;
                m2 = q;
            }else if(q > m3){
                m3 = q;
            }
            //cout << i << " " << q << endl;
        }
    }
    return max(m1+m2+L,m2+m3+2*L);
}
/*
int main(){
    int n,m,l;
    cin >> n >> m >> l;
    int a[m],b[m],t[m];
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i] >> t[i];
    }
    cout << travelTime(n,m,l,a,b,t) << endl;
}
*/

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