Submission #1243261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243261		julia_08	Dreaming (IOI13_dreaming)	C++20	100 / 100	48 ms	18376 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

using ll = long long;

const int MAXN = 1e5 + 10;
const ll INF = 1e18;

int marc_1[MAXN], marc_2[MAXN];

vector<pair<int, int>> adj[MAXN];

pair<ll, ll> dp_1[MAXN];

ll dp_2[MAXN];

void dfs_1(int v){

  marc_1[v] = 1;
  dp_1[v] = {0, 0};

  for(auto [u, w] : adj[v]){
    if(!marc_1[u]){

      dfs_1(u);

      if(dp_1[u].first + w >= dp_1[v].first){
        dp_1[v] = {dp_1[u].first + w, dp_1[v].first};
      } else dp_1[v].second = max(dp_1[v].second, dp_1[u].first + w);

    }
  }

}

vector<int> comp;

void dfs_2(int v){

  comp.push_back(v);

  marc_2[v] = 1;

  for(auto [u, w] : adj[v]){
    if(!marc_2[u]){

      ll x = dp_1[v].first;
      if(x - w == dp_1[u].first) x = dp_1[v].second;

      dp_2[u] = max(dp_2[v], x) + w;

      dfs_2(u);

    }
  }

}

int travelTime(int n, int m, int l, int a[], int b[], int t[]){

  for(int i=1; i<=n; i++){
    adj[i].clear();
    marc_1[i] = marc_2[i] = 0;
  }

  for(int i=0; i<m; i++){
    adj[a[i] + 1].push_back({b[i] + 1, t[i]});
    adj[b[i] + 1].push_back({a[i] + 1, t[i]});
  }
  
  vector<ll> prof;

  ll ans = 0;

  for(int i=1; i<=n; i++){
    if(!marc_1[i]){

      dfs_1(i);

      comp.clear();
      dfs_2(i);

      ll min_dp = INF;

      for(auto v : comp){
        ans = max(ans, dp_1[v].first + dp_1[v].second);
        min_dp = min(min_dp, max(dp_1[v].first, dp_2[v]));
      }

      prof.push_back(min_dp);

    }
  }

  sort(prof.rbegin(), prof.rend());

  if(prof.size() >= 2) ans = max(ans, prof[0] + prof[1] + l);
  if(prof.size() >= 3) ans = max(ans, prof[1] + prof[2] + 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