oj.uz

Submission #650300

# Submission time Handle Problem Language Result Execution time Memory
650300 2022-10-13T12:42:10 Z ojoConmigo Dreaming (IOI13_dreaming) C++17
0 / 100
 47 ms 13272 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;
        }
    }
}

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 13272 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 13272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6356 KB Output is correct
2 Correct 21 ms 6408 KB Output is correct
3 Correct 25 ms 6356 KB Output is correct
4 Correct 25 ms 6464 KB Output is correct
5 Correct 18 ms 6372 KB Output is correct
6 Correct 25 ms 6740 KB Output is correct
7 Correct 24 ms 6576 KB Output is correct
8 Correct 20 ms 6228 KB Output is correct
9 Correct 17 ms 6156 KB Output is correct
10 Correct 23 ms 6580 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 6 ms 3796 KB Output is correct
13 Correct 6 ms 3796 KB Output is correct
14 Correct 6 ms 3796 KB Output is correct
15 Correct 5 ms 3796 KB Output is correct
16 Correct 9 ms 3796 KB Output is correct
17 Correct 7 ms 3760 KB Output is correct
18 Correct 5 ms 3900 KB Output is correct
19 Correct 5 ms 3796 KB Output is correct
20 Incorrect 1 ms 220 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 13272 KB Output isn't correct
2 Halted 0 ms 0 KB -