oj.uz

Submission #650423

# Submission time Handle Problem Language Result Execution time Memory
650423 2022-10-13T17:43:07 Z ojoConmigo Dreaming (IOI13_dreaming) C++17
0 / 100
 45 ms 13080 KB 
#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;
        }
    }
}

int dfs2(int nodo, int p, int top){
    ans[nodo] = max(fir[nodo],top);
    int cont = ans[nodo];
    for(auto k : g[nodo]){
        int v = k.first;
        int 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++){
        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);
            int 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 45 ms 13080 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 45 ms 13080 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 6332 KB Output is correct
2 Correct 20 ms 6404 KB Output is correct
3 Correct 24 ms 6280 KB Output is correct
4 Correct 31 ms 6356 KB Output is correct
5 Correct 21 ms 6296 KB Output is correct
6 Correct 24 ms 6652 KB Output is correct
7 Correct 22 ms 6612 KB Output is correct
8 Correct 22 ms 6212 KB Output is correct
9 Correct 19 ms 6208 KB Output is correct
10 Correct 22 ms 6712 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 5 ms 3884 KB Output is correct
13 Correct 5 ms 3896 KB Output is correct
14 Correct 5 ms 3764 KB Output is correct
15 Correct 5 ms 3888 KB Output is correct
16 Correct 6 ms 3796 KB Output is correct
17 Correct 6 ms 3796 KB Output is correct
18 Correct 8 ms 3920 KB Output is correct
19 Correct 6 ms 3796 KB Output is correct
20 Incorrect 1 ms 312 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 45 ms 13080 KB Output isn't correct
2 Halted 0 ms 0 KB -