oj.uz

Submission #650424

# Submission time Handle Problem Language Result Execution time Memory
650424 2022-10-13T17:47:16 Z ojoConmigo Dreaming (IOI13_dreaming) C++17
0 / 100
 47 ms 13808 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

void dfs1(ll nodo, ll p){
    vis[nodo] = true;
    for(auto k : g[nodo]){
        ll v = k.first;
        ll w = k.second;
        if(v == p)continue;
        dfs1(v,nodo);
        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;
        }
    }
}

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

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N);
    for(int i=0; i<M; i++){
        ll x = A[i];
        ll y = B[i];
        ll 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);
    ll m1,m2,m3;
    m1 = m2 = m3 = 0;
    for(int i=0; i<N; i++){
        if(vis[i] == false){
            dfs1(i,-1);
            ll q = dfs2(i,-1,0);
            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.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 13808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 13808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6996 KB Output is correct
2 Correct 20 ms 7076 KB Output is correct
3 Correct 19 ms 6984 KB Output is correct
4 Correct 20 ms 7048 KB Output is correct
5 Correct 18 ms 6912 KB Output is correct
6 Correct 22 ms 7460 KB Output is correct
7 Correct 27 ms 7252 KB Output is correct
8 Correct 17 ms 6868 KB Output is correct
9 Correct 23 ms 6892 KB Output is correct
10 Correct 22 ms 7304 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 13808 KB Output isn't correct
2 Halted 0 ms 0 KB -