Submission #508770

#	Time	Username	Problem	Language	Result	Execution time	Memory
508770		Gurban	Dreaming (IOI13_dreaming)	C++17	100 / 100	88 ms	18656 KiB

dreaming

#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 = 0;i < M;i++){
        E[A[i]].push_back({B[i],T[i]});
        E[B[i]].push_back({A[i],T[i]});
    }
    for(int i = 0;i < N;i++) if(!vis[i]) calc(i,0);
    memset(vis,0,sizeof(vis));
    vector<pair<int,int>>v;
    for(int i = 0;i < N;i++){
        if(vis[i]) continue;
        idx = -1;
        jog = 2e9;
        dfs(i,-1,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});
    if((int)v.size() >= 3) ans = max(ans,v[1].first+v[2].first + 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