Submission #897396

#	Time	Username	Problem	Language	Result	Execution time	Memory
897396		Sir_Ahmed_Imran	Dreaming (IOI13_dreaming)	C++17	100 / 100	53 ms	17808 KiB

dreaming

                              ///~~~LOTA~~~///
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 100000
int ans;
int vis[N];
int dp1[N];
int dp2[N];
int dp3[N];
vector<pii> a[N];
void dfs(int v){
    vis[v]=1;
    for(auto& i:a[v]){
        if(vis[i.ff]) continue;
        dfs(i.ff);
        if(dp1[i.ff]+i.ss>dp1[v]){
            dp2[v]=dp1[v];
            dp1[v]=dp1[i.ff]+i.ss;
        }
        else 
            dp2[v]=max(dp2[v],dp1[i.ff]+i.ss);
    }
}
int dfs2(int v,int u){
    ans=max(ans,dp1[v]+dp2[v]);
    ans=max(ans,dp1[v]+dp3[v]);
    int o=max(dp1[v],dp3[v]);
    for(auto& i:a[v]){
        if(i.ff==u)
            continue;
        dp3[i.ff]=dp3[v]+i.ss;
        if(dp1[i.ff]+i.ss==dp1[v])
            dp3[i.ff]=max(dp3[i.ff],dp2[v]+i.ss);
        else dp3[i.ff]=max(dp3[i.ff],dp1[v]+i.ss);
        o=min(o,dfs2(i.ff,v));
    }
    return o;
}
int travelTime(int n,int m,int l,int p[] ,int q[],int t[]){
    for(int i=ans=0;i<m;i++){
        a[p[i]].append({q[i],t[i]});
        a[q[i]].append({p[i],t[i]});
    }
    vector<int> v;
    for(int i=0;i<n;i++){
        if(vis[i]) 
            continue;
        dfs(i);
        v.append(dfs2(i,-1));
    }
    sort(all(v));
    v.back()-=l;
    sort(all(v));
    reverse(all(v));
    if(v.size()>1)
        ans=max(ans,v[0]+v[1]+2*l);
    return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23