Submission #1138102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138102		mychecksedad	Dreaming (IOI13_dreaming)	C++20	100 / 100	90 ms	53952 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


vector<pii> g[N];
int dp[N], pd[N];
void dfs(int v, int p, vector<bool> &vis){
  vis[v] = 1;
  dp[v] = 0;
  for(auto [u, w]: g[v]){
    if(u != p && !vis[u]){
      dfs(u, v, vis);
      dp[v] = max(dp[v], dp[u] + w);
    }
  }
}
void reroot(int v, int p, vector<bool> &vis, vi &C){
  C.pb(v);
  vis[v] = 1;
  vector<int> pref, suf;
  for(int j = 0; j < g[v].size(); ++j){
    if(g[v][j].ff == p){
      if(pref.size()) pref.pb(pref.back());
      else pref.pb(0);
    }else{
      if(pref.size()) pref.pb(max(pref.back(), dp[g[v][j].ff] + g[v][j].ss));
      else pref.pb(dp[g[v][j].ff] + g[v][j].ss);
    }
  }
  for(int j = int(g[v].size())-1; j >= 0; --j){
    if(g[v][j].ff == p){
      if(suf.size()) suf.pb(suf.back());
      else suf.pb(0);
    }else{
      if(suf.size()) suf.pb(max(suf.back(), dp[g[v][j].ff] + g[v][j].ss));
      else suf.pb(dp[g[v][j].ff] + g[v][j].ss);
    }
  }
  reverse(all(suf));
  for(int j = 0; j < g[v].size(); ++j){
    auto [u, w] = g[v][j];
    if(u != p && !vis[u]){
      pd[u] = max(pd[v] + w, max(j == 0 ? 0 : pref[j - 1], j + 1 == int(g[v].size()) ? 0 : suf[j + 1]) + w);
      reroot(u, v, vis, C);
    }
  }
}
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<bool> vis(n);
  for(int i = 1; i <= n; ++i){
    if(!vis[i-1]) dfs(i-1, i-1, vis); 
  }
  vis.clear();
  vis.resize(n, 0);
  vector<int> val;
  int ans = 0;
  for(int i = 1; i <= n; ++i){
    if(!vis[i-1]) {
      pd[i - 1] = 0;
      vi C;
      reroot(i-1, i-1, vis, C); 
      int mn = MOD;
      for(int u: C){
        mn = min(mn, max(dp[u], pd[u]));
        ans = max({ans, dp[u], pd[u]});
      }
      val.pb(mn);
    }
  }
  for(int c: val) ans=max(c, ans);
  if(val.size() == 1){
    return ans;
  }
  sort(all(val));
  ans = max(ans, val.back() + val[int(val.size())-2] + L);
  if(val.size()>=3)
    ans = max(ans, val[int(val.size())-2] + val[int(val.size())-3] + 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