Submission #1262236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262236		enzy	Dreaming (IOI13_dreaming)	C++20	100 / 100	44 ms	16964 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
vector<pair<int,int>>v[maxn];
int pai[maxn], resp, val[maxn], at[maxn], cima[maxn], me;
pair<int,int> dp[maxn];
void dfs1(int u){
    for(pair<int,int> p : v[u]){
        int viz=p.first, w=p.second;
        if(viz==pai[u]) continue;
        pai[viz]=u;
        dfs1(viz);
        if(dp[viz].first+w>dp[u].first){
            dp[u].second=dp[u].first;
            dp[u].first=dp[viz].first+w;
        }else if(dp[viz].first+w>dp[u].second) dp[u].second=dp[viz].first+w;
    }
    resp=max(resp,dp[u].first+dp[u].second);
    val[u]=at[u]=dp[u].first;
}
void dfs2(int u){
    if(pai[u]!=u){ // se n sou a raiz
        at[u]=val[u]=max(dp[u].first,cima[u]);
    }
    me=min(me,val[u]);
    for(pair<int,int> p : v[u]){
        int viz=p.first, w=p.second;
        if(viz==pai[u]) continue;
        if(dp[u].first==dp[viz].first+w) at[u]=max(dp[u].second,cima[u]);
        else at[u]=max(dp[u].first,cima[u]);
        cima[viz]=at[u]+w;
        dfs2(viz);
    }
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
    for(int i=0;i<m;i++){
        A[i]++; B[i]++;
        v[A[i]].push_back({B[i],T[i]});
        v[B[i]].push_back({A[i],T[i]});
    }
    vector<int>process;
    for(int i=1;i<=n;i++){
        if(!pai[i]){
            me=inf;
            pai[i]=i;
            dfs1(i);
            dfs2(i);
            if(me==inf) me=0;
            process.push_back(me);
        }
    }
    sort(process.begin(),process.end());
    reverse(process.begin(),process.end());
    if(process.size()==1) return max(process[0],resp);
    if(process.size()==2) return max(process[0]+process[1]+l,resp);
    if(process.size()>=3) return max({process[0]+process[1]+l,process[1]+process[2]+2*l,resp});
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

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