Submission #964157

#	Time	Username	Problem	Language	Result	Execution time	Memory
964157		Amr	Dreaming (IOI13_dreaming)	C++17	100 / 100	93 ms	31256 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x; // % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)  ; // % mod;
        y = y>>1;
        x = (x*x) ; // % mod;
    }
    return res;
}
ll curans = -1e18;
ll inf = 1e18;
ll vis[N];
pair<ll,ll> dp[N];
ll ans[N];
ll mn = 1e18;
vector<pair<ll,ll> > v[N];
void dfs(ll x, ll par)
{
    if(vis[x]) return;
    vis[x] = 1;
    dp[x] = {0,0};
    vector<ll> vv;
    for(int i = 0; i < v[x].sz; i++)
    {
        ll newn = v[x][i].F;
        if(newn==par) continue;
        dfs(newn,x);
        vv.push_back(dp[newn].F+v[x][i].S);
    }
    sort(all(vv)); reverse(all(vv));
    if(vv.sz)  dp[x].F = vv[0];
    if(vv.sz>1)dp[x].S = vv[1];
}
void dfs2(ll x, ll par, ll w)
{
    if(vis[x]) return;
    vis[x] = 1;
    ans[x] = 0;
    if(par!=-1)
    {
        ll wh = dp[par].F;
        if(dp[x].F+w==wh) wh = dp[par].S;
        ans[x] = w+max(wh,ans[par]);
         mn = min(mn,max(dp[x].F,ans[x]));
    }
    else
    {

        mn = min(mn,dp[x].F);
    }
    curans = max(curans,dp[x].F+(dp[x].S));
    for(int i = 0; i < v[x].sz; i++)
    {
        ll newn = v[x][i].F;
        if(newn==par) continue;
        dfs2(newn,x,v[x][i].S);
    }

}
int travelTime(int N,int M,int L, int A[],int B[],int T[])
{
    for(int i = 0; i < M; i++)
    {
        ll x = A[i], y = B[i], z = T[i];
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    for(int i = 0; i < N; i++)
    {
        if(!vis[i]) dfs(i,-1);
    }
    //for(int i = 0; i < N; i++) cout << dp[i].F << " " << dp[i].S << endl; cout << endl;
    for(int i =0; i < N; i++) vis[i] = 0;
    vector<ll> curv;
    for(int i = 0; i < N; i++)
    {
        if(!vis[i])
        {
            mn = 1e18;
            dfs2(i,-1,0);
            curv.push_back(mn);
            //cout << i << " " << mn << endl;
        }
    }


    sort(all(curv)); reverse(all(curv));
    if(curv.sz==1) return curans;
    if(curv.sz==2) return max(curans,curv[0] + curv[1] + L);
    else
    {
        ll best = 1e18;
        best = min(best,max(curv[0]+curv[1]+L,curv[1]+curv[2]+2*L));
        //best = min(best,max(curv[1]+curv[0]+L,curv[0]+curv[2]+2*L));
        return max(best,curans);
    }
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(ll, ll)':
dreaming.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
dreaming.cpp: In function 'void dfs2(ll, ll, ll)':
dreaming.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < v[x].sz; 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