Submission #1276447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276447		avohado	Dreaming (IOI13_dreaming)	C++20	0 / 100	28 ms	13552 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
vector<pair<int, int>> g[maxn];
bool a[maxn];
long long k;int i1;
int dfs(int u, int p){
    if(g[u].size()<=1){
        return u;
    }
    for(auto i:g[u]){
        if(i.f!=p){
            return dfs(i.f, u);
        }
    }
}
long long dfs2(int u, int p, long long sum){
    long long mn=0;
    a[u]=1;
    for(auto i:g[u]){
        if(i.f!=p)
        mn=max(mn, dfs2(i.f, u, sum+i.s)+i.s);
    }
    if(max(mn, sum)<k){
        i1=u;
        k=max(mn, sum);
    }
    return mn;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0; i<M; i++){
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    vector<long long> v;
    for(int i=0; i<M; i++){
        if(!a[i]){
            k=INT64_MAX;
            int u=dfs(i, i);
            dfs2(u, u, 0);
            v.push_back(k);
        }
    }
    sort(v.begin(), v.end(), greater<>());
    if(v.size()>2){
        return v[0]+v[1]+L;
    }else{
        return max(v[0]+v[1]+L, v[1]+v[2]+L*2);
    }
}

Compilation message (stderr)

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

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