Submission #383501

#	Time	Username	Problem	Language	Result	Execution time	Memory
383501		mehrdad_sohrabi	Dreaming (IOI13_dreaming)	C++14	100 / 100	123 ms	19684 KiB

dreaming

#include <bits/stdc++.h>
#include"dreaming.h"
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e5+100;
vector <pii> g[N];
ll dis[N];
ll par[N];
ll vis[N];
vector <int> ras;
void dfs(ll v,ll p){
    ras.pb(v);
    vis[v]=1;
    par[v]=p;
    for (auto U : g[v]){
        ll u=U.F;
        if (u==p) continue;
        dis[u]=dis[v]+U.S;
        dfs(u,v);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i=0;i<M;i++){
        g[A[i]].pb({B[i],T[i]});
        g[B[i]].pb({A[i],T[i]});
    }
    vector <int> a;
    ll ans=0;
    for (int i=0;i<N;i++){
        if (vis[i]) continue;
        ras.clear();
        dfs(i,i);
        ll mx=0,id=i;
        for (auto u : ras){
            if (dis[u]>mx){
                mx=dis[u];
                id=u;
            }
        }
        dis[id]=0;
        ras.clear();
        dfs(id,id);
        mx=0;
        ll v=id;
        for (auto u : ras){
            if (dis[u]>mx){
                v=u;
                mx=dis[u];
            }
        }
        ll mn=1e9;
        if (v==id) mn=0;
        while (v!=id){
            mn=min(mn,max(dis[v],mx-dis[v]));
            v=par[v];
        }
        a.pb(mn);
     //   cout << mx << endl;
        ans=max(ans,mx);
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    for (int i=1;i<a.size();i++){
        ans=max(ans,(ll)a[0]+(ll)a[i]+(ll)L);
    }
    if (a.size()>2) ans=max(ans,(ll)a[1]+a[2]+2*L);
    return ans;
}
/*
int a[N],b[N],c[N];
int main(){
    sync;
    ll n,m,l;
    cin >> n >> m >> l;

    for (int i=0;i<m;i++){
        cin >> a[i] >> b[i] >> c[i];

    }
    kill(travelTime(n,m,l,a,b,c));
}

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i=1;i<a.size();i++){
      |                  ~^~~~~~~~~

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