oj.uz

Submission #1022159

# Submission time Handle Problem Language Result Execution time Memory
1022159 2024-07-13T10:39:10 Z MarwenElarbi Dreaming (IOI13_dreaming) C++17
0 / 100
 32 ms 12116 KB 
#include <bits/stdc++.h>
#include"dreaming.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int nax=1e5+5;
vector<bool> vis(nax);
pair<pair<int,int>,pair<int,int>> dp[nax];
vector<pair<int,int>> adj[nax];
int res=0;
pair<int,int> mx={-1,-1};
void init(int x,int p){
    dp[x]={{0,0},{0,0}};
    vis[x]=true;
    for(auto u:adj[x]){
        if(u.fi==p) continue;
        init(u.fi,x);
        if(u.se+dp[u.fi].fi.fi>dp[x].fi.fi){
            dp[x].se=dp[x].fi;
            dp[x].fi.fi=dp[u.fi].fi.fi+u.se;
            dp[x].fi.se=u.fi;
        }else if(u.se+dp[u.fi].fi.fi>dp[x].se.fi){
            dp[x].se.fi=dp[u.fi].fi.fi+u.se;
            dp[x].se.se=u.fi;
        }
    }
    return;
}
int ans;
void dfs(int x,int p){
    res=max(res,dp[x].fi.fi+dp[x].se.fi);
    ans=min(ans,dp[x].fi.fi);
    for(auto u:adj[x]){
        if(u.fi==p) continue;
        pair<int,int> cur;
        if(u.fi==dp[x].fi.se){
            cur=dp[x].se;
            cur.fi+=u.se;
            cur.se=x;
        }else{
            cur=dp[x].fi;
            cur.fi+=u.se;
            cur.se=x;
        }
        if(cur.fi>dp[u.fi].fi.fi){
            dp[u.fi].se=dp[u.fi].fi;
            dp[u.fi].fi=cur;
        }else if(cur.fi>dp[u.fi].se.fi){
            dp[u.fi].se=cur;
        }
        dfs(u.fi,x);
    }
}   
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for (int i = 0; i < M; ++i)
    {
        adj[A[i]].pb({B[i],T[i]});
        adj[B[i]].pb({A[i],T[i]});
    }
    vector<int> tab;
    for (int i = 0; i < N; ++i)
    {
        if(vis[i]) continue;
        init(i,-1);
        dfs(i,-1);
        tab.pb(ans);
    }
    sort(tab.rbegin(),tab.rend());
    if(tab.size()>1) res=max(res,tab[0]+tab[1]+L);
    if(tab.size()>2) res=max(res,tab[1]+tab[2]+2*L);
    return res;
}/*
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n,m,l;
    cin>>n>>m>>l;
    int a[m];
    int b[m];
    int 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 Correct 27 ms 12116 KB Output is correct
2 Correct 32 ms 11860 KB Output is correct
3 Correct 19 ms 10584 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 5072 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Incorrect 1 ms 4440 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12116 KB Output is correct
2 Correct 32 ms 11860 KB Output is correct
3 Correct 19 ms 10584 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 5072 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Incorrect 1 ms 4440 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12116 KB Output is correct
2 Correct 32 ms 11860 KB Output is correct
3 Correct 19 ms 10584 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 5072 KB Output is correct
6 Correct 8 ms 5980 KB Output is correct
7 Incorrect 1 ms 4440 KB Output isn't correct
8 Halted 0 ms 0 KB -