oj.uz

Submission #1022155

# Submission time Handle Problem Language Result Execution time Memory
1022155 2024-07-13T10:35:36 Z MarwenElarbi Dreaming (IOI13_dreaming) C++17
14 / 100
 29 ms 12124 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]});
    }
    for (int i = 0; i < N; ++i)
    {
        if(vis[i]) continue;
        init(i,-1);
        ans=1e9;
        dfs(i,-1);
        if(mx.fi<ans){
            mx.se=mx.fi;
            mx.fi=ans;
        }else if(mx.se<ans){
            mx.se=ans;
        }
    }
    if(M==N-1) return res;
    res=max(res,mx.fi+mx.se+L);
    if(M==0) res=max(res,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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12124 KB Output is correct
2 Correct 28 ms 11860 KB Output is correct
3 Correct 19 ms 10588 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 8 ms 6032 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 15 ms 7288 KB Output is correct
9 Correct 20 ms 9308 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 26 ms 9740 KB Output is correct
12 Correct 29 ms 10832 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct

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 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4560 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4456 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12124 KB Output is correct
2 Correct 28 ms 11860 KB Output is correct
3 Correct 19 ms 10588 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 8 ms 6032 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 15 ms 7288 KB Output is correct
9 Correct 20 ms 9308 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 26 ms 9740 KB Output is correct
12 Correct 29 ms 10832 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4560 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4456 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Incorrect 1 ms 4444 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7260 KB Output is correct
2 Incorrect 13 ms 7256 KB Output isn't correct
3 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 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4560 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4456 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12124 KB Output is correct
2 Correct 28 ms 11860 KB Output is correct
3 Correct 19 ms 10588 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 8 ms 6032 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 15 ms 7288 KB Output is correct
9 Correct 20 ms 9308 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 26 ms 9740 KB Output is correct
12 Correct 29 ms 10832 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4560 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4456 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Incorrect 1 ms 4444 KB Output isn't correct
29 Halted 0 ms 0 KB -