oj.uz

Submission #508251

# Submission time Handle Problem Language Result Execution time Memory
508251 2022-01-13T07:52:12 Z Gurban Dreaming (IOI13_dreaming) C++17
0 / 100
 92 ms 16064 KB 
#include "bits/stdc++.h"
#include "dreaming.h"
using namespace std;

const int maxn=1e5+5;
int idx,jog,ans;
int dp[maxn][2];
bool vis[maxn];
vector<pair<int,int>>E[maxn];

void calc(int nd,int pr){
    vis[nd] = 1;
    int a = 0,b = 0;
    for(auto i : E[nd]){
        if(i.first == pr) continue;
        calc(i.first,nd);
        if(dp[i.first][0] + i.second > a) b=a,a = dp[i.first][0] + i.second;
        else if(dp[i.first][0] + i.second > b) b=dp[i.first][0] + i.second;
    }
    dp[nd][0] = a;
    dp[nd][1] = b;
    ans = max(ans,a + b);
}

void dfs(int nd,int pr,int yok){
    vis[nd] = 1;
    if(max(yok,dp[nd][0]) < jog){
        idx = nd;
        jog = max(yok,dp[nd][0]);
    }
    for(auto i : E[nd]){
        if(i.first == pr) continue;
        if(dp[i.first][0] + i.second == dp[nd][0]) dfs(i.first,nd,max(yok,dp[nd][1])+i.second);
        else dfs(i.first,nd,max(yok,dp[nd][0])+i.second);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 1;i <= M;i++){
        E[A[i]].push_back({B[i],T[i]});
        E[B[i]].push_back({A[i],T[i]});
    }
    for(int i = 1;i <= N;i++) if(!vis[i]) calc(i,0);
    memset(vis,0,sizeof(vis));
    vector<pair<int,int>>v;
    for(int i = 1;i <= N;i++){
        if(vis[i]) continue;
        idx = -1;
        jog = 1e9;
        dfs(i,0,0);
        v.push_back({jog,idx});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(M != N-1) ans = max(ans,v[0].first + v[1].first + L);
    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 16064 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 6856 KB Output is correct
2 Incorrect 30 ms 6884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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